If you see a message like the below when you are trying to connect to your VPS using SSH, it's completely normal if you have just reinstalled your VPS.

@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@    WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED!     @
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
IT IS POSSIBLE THAT SOMEONE IS DOING SOMETHING NASTY!

SSH keys are re-generated when you reinstall your operating system, so your computer warns you regarding this.

You can simply ignore this message and follow the instructions given with the message to resolve the issue.

Simply edit your known_hosts file shown in the message and remove the offending line.

You might just run ssh-keygen -f "<somelocation>/.ssh/known_hosts" -R "<yourVPSIP>" as well if it's shown in the message.

Then you can simply retry connecting and then accept the new key.