Mike,
By default the sshd_config file in Ubuntu 12.04 LTS (If that is what you are using Debian and Mint should work the same) in /etc/ssh should have the following defaults set under # Authentication:
StrictMode yes
RSAAuthentication yes
PubkeyAuthentication yes
You should not have to change any of these settings. With these 3 settings set to "yes" RSA, and public keys are automacally activated for use. Ubuntu will first search for an "authorize_key" in the ~/.ssh directory if it finds it it will try and resolve the id_rsa key pairs. If these keys no longer match then you will get a failed to connect error in the terminal. Only IF it doesn't find an "authorize_key" will it default to the "known_host" file.
So If you are still having issues connecting and you see that you have an "authorize_key" file in ~/.ssh then try renaming it as well as removing the "known_hosts" and restarting ssh either by:
sudo /etc/init.d/ssh restart
or
sudo service ssh reload
Then try a basic ssh into the host from the client to reestablish the "known_host file. If you are able to log on then proceed to generate new keys per Method 2 and copy them to the host machine by Method 1.
Goog luck
--
James