Sometimes ‘ssh’ doesn’t behave as you were hoping. Here are some things to check when it goes awry.

Recall that you may have created your public/private key-pair like this:
ssh-keygen -t rsa -C "[email protected]"

You might have even gone for a heftier bit-length, or even used PKCS8:
ssh-keygen -t rsa -C "[email protected]" -b 4096 -m PKCS8

And you might have remembered to chmod the .ssh folder as 700, and any private keys as 600.

“Someone stole my laptop and got my private keys”
As quickly as you can, go delete the ~/.ssh/authorized_keys file on your destination computers. If your laptop was encrypted with FileVault you don’t have to rush.
1. update your authorised_keys file with new public keys
2. $ for host in machine1.com othermachine machine3.elsewhere.com; do scp ~/.ssh/authorized_keys $host:.ssh/; done

Do not trust the security you thought you had due to the passphrase on your private key (created by ssh-keygen) since brute forcing the passphrase only takes a few hours (read here) unless you upgraded to a more secure private key format like PKCS#8 (transparently supported by OpenSSL).
$ mv my_rsa_key my_rsa_key.old
$ openssl pkcs8 -topk8 -v2 des3 \
-in my_rsa_key.old -passin 'pass:snoopy loves secrets too' \
-out test_rsa_key -passout 'pass:snoopy loves secrets too'

Grab Brendan’s keycrypt script here.

“My private keys no longer work under 10.9 (Mavericks).”
Some suggest that Apple removed support for PKCS#8 private keys (sh-agent and keychain stopped supporting PKCS#8 ??).  You may need to undo your encryption or switch to AES256.
$ mv ~/.ssh/id_rsa_mykey ~/.ssh/id_rsa_mykey.pkcs8
$ openssl pkcs8 -in ~/.ssh/id_rsa_mykey.pkcs8 -out ~/.ssh/id_rsa_mykey
$ chmod 600 ~/.ssh/id_rsa_mykey
$ ssh-keygen -f ~/.ssh/id_rsa_mykey -p

A guy named ‘Joe’ suggested that manually adding the encrypted key, does work in 10.9:
# empty the ssh-agent and add the private encrypted key
ssh-add -D
ssh-add ~/.ssh/id_rsa

He then suggests that just reinstalling openssl solves the problem too:
brew update
brew install openssl
brew link openssl --force
brew install openssh

Finally, newer versions of ssh-keygen seem to handle PKCS#8 so openssl no longer needs to be called. Note that Windows users are out-a-luck using puttygen which doesn’t support PKCS#8.

“Roaming not allowed by server”
: Ensure that /etc/ssh/sshd_config has HostbasedAuthentication set to yes.
Remember to restart the ssh daemon: kill -HUP `cat /var/run/sshd.pid`

If you are dealing with a SynlogyDS5, and you don’t want to ssh into root, then you’ll quickly discover that ‘sudo’ won’t exist until you install it with ipkg update; ipkg install sudo. Of course, ‘ipkg’ isn’t available either (ipkg is for installing stuff that is not available in the package center), so start with that (link). Remember to add admin to the sudoers (link).

: Ensure your file permissions are correct.
As the default permissions on a SynlogyDS5 might be 777 (hard to believe) for the home folder of admin, set it them to 755 (in addition to 700 for .ssh/ and 600 for authorized_keys) and you’re good to go.