How to solve SSH error: REMOTE HOST IDENTIFICATION HAS CHANGED!

Problem:

A server which I regularly used to connect to using SSH one day gave me the following error:

@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@    WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED!     @
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
IT IS POSSIBLE THAT SOMEONE IS DOING SOMETHING NASTY! [Read more…]