The SSH installation on your VPS has a host key that is generated on deployment for your VPS. When you reinstall the VPS, this host key will be regenerated.
If you then try to log in with SSH with a computer where you've saved the previous installation's host key, you will receive the following scary-looking message:
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@ WARNING: POSSIBLE DNS SPOOFING DETECTED! @
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
The ECDSA host key for vm.ext.cekkent.net has changed,
and the key for the corresponding IP address 1.2.3.4
is unknown. This could either mean that
DNS SPOOFING is happening or the IP address for the host
and its host key have changed at the same time.
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@ 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 a host key has just been changed.
The fingerprint for the ECDSA key sent by the remote host is
SHA256:aE5WznPHvx3jSrGx2JvfqEKHn2OW44/A6zhCSg+7OsI.
Please contact your system administrator.
Add correct host key in /Users/user/.ssh/known_hosts to get rid of this message.
Offending ECDSA key in /Users/user/.ssh/known_hosts:1983
ECDSA host key for vm.ext.cekkent.net has changed and you have requested strict checking.
Host key verification failed.
You can easily fix this by removing the old host key with the following command:
ssh-keygen -R ip.or.computer, where "ip.or.computer" is exactly the same string that you were using with the ssh command:
% ssh-keygen -R test.domain.com
# Host test.domain.com found: line 1983
/Users/user/.ssh/known_hosts updated.
Original contents retained as /Users/user/.ssh/known_hosts.old
%
Proceed as normal thereafter.