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.