ssh: "Agent admitted failure to sign using the key"

I'm trying to set up password-less login with ssh on Ubuntu Server, but I keep getting:

Agent admitted failure to sign using the key

and prompt for password.

I have generated new rsa keys. Before the system reboot it worked just fine.

All the links lead me to this bug, but nothing works. SSH Agent is still not running.

How to fix that? Maybe the files need specific permissions?

From serverfault takeshin

• just run:

  ssh-add

  on the client (your pc)

  From

• This problem involves two machines. WHich was re-booted? ssh-add will only add the key on the client. If the key isn't accepted, there isn't a client error and a server error will only show up if the -v option is used when ssh is invoked on the client, to request the connection.

  I suppose its possible too that Ubuntu the package has, for some unknown reason, altered the error message shown. It isn't an error issued by openSSH-server, as it is used in Debian (or anywhere else I've seen it, e.g. RHEL, CentOS, Knoppix, others).

  From JohnC