When you logging into a Linux box using ssh, the Linux where you are logging from will ask you to validate the authenticity of the key presented by that host.

Once you answer yes, that key will be stored. Future logging attempts to that same server will check they key against what is stored in the file:

~/.ssh/known_hosts

If they do not match, may mean that someone is in the middle trying to capture your password, so be careful when you see some alert like this:

@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@ 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
5c:0b:18:56:b6:cd:12:10:32:cd:1d:a2:9a:cd:e5:1c.
Please contact your system administrator.
Add correct host key in /home/user/.ssh/known_hosts to get rid of this message.
Offending key in /home/user/.ssh/known_hosts:3
RSA host key for server.mydomain.com has changed and you have requested strict checking.
Host key verification failed. 

Now you have a lot of options, I usually used this one:

Using vi

Considering that the offending key is in line 3 do this:

vi $HOME/.ssh/know_hosts

Then enter

:3

to go to line 3, then, press dd to delete the line. and finally save and close the file with:

Thanks to: Grahame Kelly

:wq

The other option is easier:

Using command line

Just enter this command:

ssh-keygen -R g.garron.me

If the server you are trying to access is g.garron.me

From the man page:

-R hostname Removes all keys belonging to hostname from a known_hosts file. This option is useful to delete hashed hosts

As I said before, use this with care, and only modify your .ssh/know_hosts if you know why the key on the other side host has changed.