I had reformatted one of my hypervisor boxes (prox) and completely forgot about changing my SSH keys on other systems. I have a jumpbox that allows me to remotely access and admin the environment, but I couldn’t SSH into my prox system:

@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@ 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
2a:35:00:00:c7:e8:f3:fe:f7:6e:cf:00:00:db:e9:d8.
Please contact your system administrator.
Add correct host key in /root/.ssh/known_hosts to get rid of this message.
Offending key in /root/.ssh/known_hosts:33
RSA host key for prox1 has changed and you have requested strict checking.
Host key verification failed.

Opening up my /root/.ssh/known_hosts file I see a bunch of giberish. Answer found from c0rp.

Fast and easy fix
sed -i '33d' ~/.ssh/known_hosts
Obviously change the ’33d’ to reflect your line number. e.g line 12 wouild be ’12d’
Then SSH to your machine again and you’ll be asked if you want to store the new RSA fingerprint.

Or you can use SSH Keygen
ssh-keygen -R yourmachinenamehere