SSH Key Error, sudo works fine

Solution 1:

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.

Solution 2:

The known_hosts file contains the keys from hosts which you have previously connected to, and have verified that you have checked the key signature is correct.

In your case, one of two things has happened,

1. The key on the server has changed since you approved it for your account, but not since it was approved for the root account.
2. There is an attacker intercepting communications between you and the server, and you have approved their key for the root account and have the correct key in your account.

Most likely is case 1 - man-in-the-middle attacks on SSH, while possible, are relatively rare. The warning is there to alert you to the fact that someone may be intercepting you communications, even though the chances of this are quite low.

To resolve this, open the known_hosts file and remove the entry for the host in question. Contact the System Administrator for the host and ask them for the 'Host Key Fingerprint'. Make your connection again, verify that the fingerprint matches the one you get from the System Administrator and approve the key.

If the fingerprint does not match the one supplied by the System Administrator of the remote host, DO NOT approve the key!!