Maybe the default 2048 bit rsa key is better?Vogt 01:54, 31 August 2008 (EDT)
Sometimes the 'ssh-add' is not enough to log in without a password. It is possible that ssh is configured in such way that only a limited group of users is allowed to the machine. In this case - you need root-access to the server! - you have to change the configuration-file. Mostly you can find it as /etc/ssh/sshd_config. If the last line(s) of this file read(s): 'AllowUsers <username>', you will have to add a similar line with your own username. Don't forget to restart the ssh deamon: '/etc/init.d/sshd restart'.
bdheeman: IMHO using a personal and overly modified prompt 'mith@middleearth||~:~ >' can quite confusing for newbies.
Using pam_ssh module
I just want to add that one could also use the pam_ss module, available here http://pam-ssh.sourceforge.net/ or in the AUR to decrypt the ssh key on login and automatically start ssh-agent and add the keys. This way one would have a truely password less ssh session and in the same way not compromise security by using a passphrase less key.