SSH: Agent Admitted Failure To Sign Using The Key Error And Solution

I've recently regenrated and uploaded a new public ssh-key using the ssh-copy-id command. Now I'm getting the following error:

ssh root@server3
Agent admitted failure to sign using the key.
root@server3's password:

How do I fix this problem?

To fix this problem you need logout of your Unix / Linux / OS X / BSD desktop session and log back in again to force the agent to forget identity. Another option is to run the ssh-add command to add RSA or DSA identities to the authentication agent. This will fix your problem without login out from the current session:
$ ssh-add