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?