For a Linux VPS, all you have to do to generate new hostkeys on the server is use ssh-keygen (included with the standard OpenSSH package) to perform the following commands for both SSH protocols (ultimately you must perform all three commands). Make sure that the -N is followed by two single quotation marks and that all three file names are different.
SSH1 protocolFor the SSH1 protocol you only require an RSA1 key:
ssh-keygen -f /etc/ssh/ssh_host_key -N '' -t rsa1
ssh-keygen -f /etc/ssh/ssh_host_rsa_key -N '' -t rsa
ssh-keygen -f /etc/ssh/ssh_host_dsa_key -N '' -t dsa
The authenticity of host xxx can't be established
On Linux this is stored in ~/.ssh/known_hosts
On Windows it is stored in the registry under HKEY_CURRENT_USER\Software\SimonTatham\PuTTY\SshHostKeys
Every time a connection is established, a comparison of the fingerprints (which look something like xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx (for rsa)) is made between the local database and the server you are contacting.
You can remove the locally saved cache for the server and re-establish the connection, in which case you will be prompted to save the fingerprint again. On a Linux terminal, you will see the following warning:Offending key in /home/USER/.ssh/known_hosts:15
where /home/USER/.ssh/known_hosts is the file location and 15 is the line number. This enables you to use vi to jump directly to the right line so you can delete it:
vi /home/USER/.ssh/known_hosts +15
For Windows, you use regedit to find the correct registry entry and delete the offending key: