This error appears to only occur on Linux systems. For more details, see this issue report.
ssh -vT git@github.com
# ...
# Agent admitted failure to sign using the key.
# debug1: No more authentication methods to try.
# Permission denied (publickey).

Resolution

For most users, simply running ssh-add to load your keys into the SSH agent will fix this issue.
 
ssh-agent bash 
 
ssh-add 
 
# Enter passphrase for /home/you/.ssh/id_rsa: [tippy tap]
# Identity added: /home/you/.ssh/id_rsa (/home/you/.ssh/id_rsa)

If your key does not have the default filename, you'll have to pass the path to ssh-add
 
ssh-add ~/.ssh/my_other_key
# Enter passphrase for /home/you/.ssh/my_other_key: [tappity tap tap]
# Identity added: /home/you/.ssh/my_other_key (/home/you/.ssh/my_other_key)