How to fix "ssh-agent refused operation" on Ubuntu 17.10?

I installed Ubuntu 17.10 on a machine and created an ssh key. However I am not able to use the gnome keyring to unlock this ssh key, I always get the following error message when trying to connect via ssh or use my ssh key with git:

sign_and_send_pubkey: signing failed: agent refused operation

I found a lot of threads and questions regarding this message, but nothing did solve my problem.. Some outputs from my system:

$ env | grep -i ssh
    SSH_AUTH_SOCK=/run/user/1000/keyring/ssh
    SSH_AGENT_PID=1139

$ ps aux | grep -i 'agent\|keyring'
    username    997  0.0  0.1 509344  8064 ?        Sl   15:15   0:00 /usr/bin/gnome-keyring-daemon --daemonize --login
    username   1139  0.0  0.0  11240   324 ?        Ss   15:15   0:00 /usr/bin/ssh-agent /usr/bin/im-launch env GNOME_SHELL_SESSION_MODE=ubuntu gnome-session --session=ubuntu

$ ssh-add -l
    4096 SHA256:fingerprintXXX username@machine (RSA)

I installed ubuntu again inside a virtual machine and if try to use ssh or git with ssh key there the graphical passphrase dialog pops up and asks for my password flawlessly.

The agent works, it just does not cooperate because it thinks you are doing something unsafe.

The most common case is due to wrong permissions of your ssh key files. For example, if you copied them from another computer; ensure the ~/.ssh folder has 700 permissions (only accessible by you), and likewise, the files in there should not be readable by others.

chmod 700 ~/.ssh
chmod 600 ~/.ssh/*