I recently got around to updating my file server's operating system (from Mint 16 to Mint 17) and, in accordance with the law of unintended consequences, I found that I could no longer access my files using secure shell!
What I did get was an error message telling me that the host key verification [test had] failed. When you think about it, I should have anticipated the problem, after all, the original key was hashed under a different implementation of SSH Server as well as a different operating system! Fortunately, the fix is quite simple, particularly if you're only connecting to one host.
For a Single Host
Navigate to to the .ssh folder in the home/username directory (username will be unique to your circumstances). Remember that the period (full stop) indicates that this is a hidden folder, so you should ensure that you have the Show Hidden Files option enabled in your file browser. Delete the known_hosts file in the .ssh directory.
Now reconnect with your SSH host and a new key will be created following the usual warning that this is a new (and unknown!) host.
For Multiple Hosts
The error message will identify a line number in the know_hosts file; make a note of the number and open a terminal:
gksu gedit /home/username/.ssh/known_hosts
You will be prompted for your password. When the file is opened, delete the offending line, save the file and reconnect with your server. You should be prompted to recreate the key as if this were a first connection.
If you accidentally delete the wrong line (or the whole file, for that matter), fear not, the individual keys will be recreated when you next connect to your SSH server(s).
Sources & Resources: