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