WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED!

When I ssh into a server I get this message;

@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@    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
[long list of characters..].
Please contact your system administrator.

To get rid of this message I opened the known hosts file on my machine;

vi /home/user/.ssh/known_hosts

I then removed the line for the server I am trying to ssh into and saved the file. Next time I tried to ssh into the server I got the option to add it to my list of known hosts which I accepted.

This warning can appear when Linux is reinstalled or UNIX with OpenSSH.