When using SSH to connect to your VPS, if you have connected to it before, your SSH client will verify that it is providing the same "host key" as before to ensure that you're connecting securely to the correct host and not to an attacker. If you have reinstalled your VPS, then your VPS will have a new host key and so this error is expected.
The error message appears similar to the following:
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@ 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 host key has just been changed.
The fingerprint for the key sent by the remote host is
FINGERPRINT DISPLAYED HERE
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:219
remove with:
ssh-keygen -f '/home/username/.ssh/known_hosts' -R 'example.com'
Host key for example.com has changed and you have requested strict checking.
Host key verification failed.
You can remove the old host key from the file using the ssh-keygen command:
ssh-keygen -R HOSTNAME
Replace HOSTNAME with either the DNS name or IP address of the VPS you are attempting to SSH to. Your SSH client stores records for host keys for DNS names and IP addresses seperately, so you may find if you only remove the old key for the IP address and later connect with the DNS name then the error will occur again until you remove the old key for the DNS name too.
