gpg-agent is not allowed to handle ssh keys by gnome-keyring

I had the same problem (same symptoms)

sam@xxxxx:~/.ssh$ ssh [email protected]
sign_and_send_pubkey: signing failed: agent refused operation
Permission denied (publickey,gssapi-keyex,gssapi-with-mic).
... but the solution was different.

The problem was coming from the use of GNOME-KEYRING. The post referring to the solution may be read here.

In short:

Detect the problem by adding SSH_AUTH_SOCK=0 in front of the ssh command. sam@xxxxx:~/.ssh$ SSH_AUTH_SOCK=0 ssh [email protected]
In case it succeed to connect. Open the application StartUp Application (by using the search function of the Desktop for example) and disable the use of gnome-keyring.
Reboot
The page provide other details in case of similar problem with different solution.