The first time you connect to a server, you are prompted to accept the fingerprint for the host you are connecting to. The fingerprint is a combination of a digital signature, the host name and the IP address of the server. When you do accept, the fingerprint is saved in
~/.ssh/known_hosts as being a "trusted" host.
For some reason, the server's fingerprint has changed since the first time you connected to it. This may be because it is not the server you expect it to be, for example when your request is being intercepted and redirected to a different server. Hence the security warning. The explanation might also be less malicious, for example when the server was replaced/reinstalled without restoring it's previous digital signature, or when the IP address has changed.
If despite the security warning, you still trust the server you are connecting to, you should open
~/.ssh/known_hosts and look for the line starting with the address of the server you are connecting to. Remove the entire line and save your changes, then reconnect to the server. The first time you connect, it should again prompt you to accept the updated fingerprint, after which you should have no more troubles connecting to that host.
The reason why it would work with
sudo is because in those conditions you are running it as a different user (root), and each user has it's own known_hosts file (for root this is located at
/private/var/root/.ssh/known_hosts). root may have never recorded the previous fingerprint of that host, and therefor has no way of comparing it to the current one, and no reason to distrust the server.