Comment 18 for bug 505278

The culprit is gpg-keyring-daemon. It subverts the normal operation of ssh-agent, mostly just so that it can pop up a pretty box into which you can type the passphrase for an encrypted ssh key. And it paws through your .ssh directory, and automatically adds any keys it finds to your agent. And it won't let you delete those keys. How do we hate this? Let's not count the ways -- life's too short.

The failure is compounded because newer ssh clients automatically try all the keys in your ssh-agent when connecting to a host. If there are too many, the server will reject the connection. And since gnome-keyring-daemon has decided for itself how many keys you want your ssh-agent to have, and has autoloaded them, AND WON'T LET YOU DELETE THEM, you're toast.

What you really want to do is to turn off gpg-keyring-daemon altogether. Go to System --> Preferences --> Startup Applications, and unselect the "SSH Key Agent (Gnome Keyring SSH Agent)" box -- you'll need to scroll down to find it.

You'll still get an ssh-agent, only now it will behave sanely: no keys autoloaded, you run ssh-add to add them, and if you want to delete keys, you can. Imagine that.