Was getting this error on an ASA when trying to connect to it via SSH with a Perl script on a CentOS box. I was getting pretty frustrated since I had just rebuilt two identical ASAs and the script worked on one but not the other. Then it occurred to me that the one I was having issues with had the same name as a old ASA we had used in the past. Turns out that the CentOS Linux box was picking up on the old SSH finger print and not allowing the connection. A quick direct SSH to the ASA from the server showed me the issue quite clearly…
[user@server ~]$ ssh <ASA NAME>
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@ WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED! @
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
IT IS POSSIBLE THAT SOMEONE IS DOING SOMETHING NASTY!
Someone could be eavesdropping on you right now (man-in-the-middle attack)!
It is also possible that the RSA host key has just been changed.
The fingerprint for the RSA key sent by the remote host is
78:3d:15:1k:d8:0h:e7:f2:4f:6a:12:1e:2a:e8:3g:91.
Please contact your system administrator.
Add correct host key in /home/<USERNAME>/.ssh/known_hosts to get rid of this message.
Offending key in /home/<USERNAME>/.ssh/known_hosts:6
RSA host key for <ASA NAME> has changed and you have requested strict checking.
Host key verification failed.
I did as it said and cleared it out of the of the known_hosts file. After that, it worked perfectly. So lesson learned on this one, hope this saves someone else from 30 minutes of frustration.