I was trying all morning to ssh into a server with the public key authentication. There's a page about troubleshooting the public key authentication. I suspected the server is so old it uses ssh 1.5, but no. I can't think of something else beside googling on the error message:
Agent admitted failure to sign using the key.
And there it is: a bug on ubuntu.
