I just spent 30 minutes trying to get login via public key working on a new server, and here’s a few tips that I wish I knew earlier :

SSH has a verbose mode i didn’t know about - just add the -v option. Unfortunately this wasn’t particularly useful.

> ssh -v dave@new-server.com
OpenSSH_5.2p1, OpenSSL 0.9.8l 5 Nov 2009
debug1: Reading configuration data /etc/ssh_config
debug1: Connecting to new-server.com [12.34.56.78] port 22.
debug1: Connection established.
debug1: identity file /Users/dave/.ssh/identity type -1
debug1: identity file /Users/dave/.ssh/id_rsa type 1
debug1: identity file /Users/dave/.ssh/id_dsa type -1
debug1: Remote protocol version 2.0, remote software version OpenSSH_4.3
debug1: match: OpenSSH_4.3 pat OpenSSH_4*
debug1: Enabling compatibility mode for protocol 2.0
debug1: Local version string SSH-2.0-OpenSSH_5.2
debug1: SSH2_MSG_KEXINIT sent
debug1: SSH2_MSG_KEXINIT received
debug1: kex: server->client aes128-ctr hmac-md5 none
debug1: kex: client->server aes128-ctr hmac-md5 none
debug1: SSH2_MSG_KEX_DH_GEX_REQUEST(1024<1024<8192) sent
debug1: expecting SSH2_MSG_KEX_DH_GEX_GROUP
debug1: SSH2_MSG_KEX_DH_GEX_INIT sent
debug1: expecting SSH2_MSG_KEX_DH_GEX_REPLY
debug1: Host 'new-server.com' is known and matches the RSA host key.
debug1: Found key in /Users/dave/.ssh/known_hosts:8
debug1: ssh_rsa_verify: signature correct
debug1: SSH2_MSG_NEWKEYS sent
debug1: expecting SSH2_MSG_NEWKEYS
debug1: SSH2_MSG_NEWKEYS received
debug1: SSH2_MSG_SERVICE_REQUEST sent
debug1: SSH2_MSG_SERVICE_ACCEPT received
debug1: Authentications that can continue: publickey,gssapi-with-mic,password
debug1: Next authentication method: publickey
debug1: Trying private key: /Users/dave/.ssh/identity
debug1: Offering public key: /Users/dave/.ssh/id_rsa
debug1: Authentications that can continue: publickey,gssapi-with-mic,password
debug1: Trying private key: /Users/dave/.ssh/id_dsa
debug1: Next authentication method: password
dave@new-server.com's password:

Tailing /var/log/secure on the target machine is a lot more useful :

> sudo tail -f /var/log/secure
Sep 14 01:26:31 new-server sshd[22107]: Authentication refused: bad ownership or modes for directory /home/dave/.ssh
Sep 14 01:26:46 new-server sshd[22108]: Connection closed by 98.76.54.32

Finally we’re getting somewhere - bad ownership or modes for directory /home/dave/.ssh.

SSH doesn’t like it if your home or ~/.ssh directories have group write permissions. Your home directory should be writable only by you, ~/.ssh should be 700, and authorized_keys should be 600 :

> chmod g-w /home/your_user
> chmod 700 /home/your_user/.ssh
> chmod 600 /home/your_user/.ssh/authorized_keys

You can also get around this by adding StrictModes off to your ssh_config file, but I’d advise against it - fixing permissions is the way to go.