Problem with shared ssh keys

Following the process I've used in other environments, I've tried setting-up shared keys between my Mac and my CentOS 4 webserver. I've seen the same problem with my older Ubuntu 7.10 workstation trying to connect via keys to the same webserver.

I have tried both dsa and rsa keytypes (sshkeygen -t <type>).

The sshd_config file on my webserver seems to be allowing key-based logins:

RSAAuthentication yes
PubkeyAuthentication yes
AuthorizedKeysFile      .ssh/authorized_keys

And my .ssh/authorized_keys has my dsa and rsa keys added.

Where should I be looking for what to change next to make key-based logins "Just Work™"?

Is it related to the line,

#UseDNS yes

and sshd is trying to do a reverse-lookup on my IP, but cannot because it's NAT'd?

~/.ssh/ permissions should be set 0700, and the contents should be 0600.

Also, permissions on ~/ must be 0755 or less; that is, it cannot be writable by any other users.

This Ubuntu page on SSH Keys is good reading (look at Troubleshooting).

add some -v option when you initiate your ssh connection as

ssh <user>@<host> -vvv 

If ever you have the admin rights to the server, you could also strace -f -p SSHD_PID your sshd

Both of them will give you a bunch of info....