[SOLVED] Github not recognizing ssh key

Github not recognizing ssh key

I've been using ssh keys with github for a while now. Suddenly i can't push and I'm getting a Permission denied (publickey) error. Here's what I've tried so far:

Checked the ssh key is in the correct directory (~/.ssh)
Tried reuploading my public key to github (I get a message that the key already exists)
Double checked that the output of ssh-add -l -E sha256 on my system agrees with the string in my ssh settings on my github account
Followed all the steps in the "Troubleshooting ssh" section of the github docs. (Everything seems gucci)
Banged my head against the wall for an hour

So far nothing has helped. This is my last resort. I'll greatly appreciate any and all suggestions. Here's the output of my ssh -vT git@github.com

OpenSSH_7.2p2 Ubuntu-4ubuntu2.10, OpenSSL 1.0.2g  1 Mar 2016
debug1: Reading configuration data /home/MY_USER_NAME/.ssh/config
debug1: Reading configuration data /etc/ssh/ssh_config
debug1: /etc/ssh/ssh_config line 19: Applying options for *
debug1: Connecting to github.com [140.82.114.3] port 22.
debug1: Connection established.
debug1: identity file /home/MY_USER_NAME/.ssh/id_rsa type 1
debug1: key_load_public: No such file or directory
debug1: identity file /home/MY_USER_NAME/.ssh/id_rsa-cert type -1
debug1: key_load_public: No such file or directory
debug1: identity file /home/MY_USER_NAME/.ssh/id_dsa type -1
debug1: key_load_public: No such file or directory
debug1: identity file /home/MY_USER_NAME/.ssh/id_dsa-cert type -1
debug1: key_load_public: No such file or directory
debug1: identity file /home/MY_USER_NAME/.ssh/id_ecdsa type -1
debug1: key_load_public: No such file or directory
debug1: identity file /home/MY_USER_NAME/.ssh/id_ecdsa-cert type -1
debug1: key_load_public: No such file or directory
debug1: identity file /home/MY_USER_NAME/.ssh/id_ed25519 type -1
debug1: key_load_public: No such file or directory
debug1: identity file /home/MY_USER_NAME/.ssh/id_ed25519-cert type -1
debug1: Enabling compatibility mode for protocol 2.0
debug1: Local version string SSH-2.0-OpenSSH_7.2p2 Ubuntu-4ubuntu2.10
debug1: Remote protocol version 2.0, remote software version babeld-fb957b4d
debug1: no match: babeld-fb957b4d
debug1: Authenticating to github.com:22 as 'git'
debug1: SSH2_MSG_KEXINIT sent
debug1: SSH2_MSG_KEXINIT received
debug1: kex: algorithm: curve25519-sha256@libssh.org
debug1: kex: host key algorithm: rsa-sha2-512
debug1: kex: server->client cipher: chacha20-poly1305@openssh.com MAC: <implicit> compression: none
debug1: kex: client->server cipher: chacha20-poly1305@openssh.com MAC: <implicit> compression: none
debug1: expecting SSH2_MSG_KEX_ECDH_REPLY
debug1: Server host key: ssh-rsa SHA256:nThbg6kXUpJWGl7E1IGOCspRomTxdCARLviKw6E5SY8
debug1: Host 'github.com' is known and matches the RSA host key.
debug1: Found key in /home/MY_USER_NAME/.ssh/known_hosts:4
debug1: rekey after 134217728 blocks
debug1: SSH2_MSG_NEWKEYS sent
debug1: expecting SSH2_MSG_NEWKEYS
debug1: SSH2_MSG_NEWKEYS received
debug1: rekey after 134217728 blocks
debug1: SSH2_MSG_EXT_INFO received
debug1: kex_input_ext_info: server-sig-algs=<ssh-ed25519-cert-v01@openssh.com,ecdsa-sha2-nistp521-cert-v01@openssh.com,ecdsa-sha2-nistp384-cert-v01@openssh.com,ecdsa-sha2-nistp256-cert-v01@openssh.com,sk-ssh-ed25519-cert-v01@openssh.com,sk-ecdsa-sha2-nistp256-cert-v01@openssh.com,rsa-sha2-512-cert-v01@openssh.com,rsa-sha2-256-cert-v01@openssh.com,ssh-rsa-cert-v01@openssh.com,ssh-dss-cert-v01@openssh.com,sk-ssh-ed25519@openssh.com,sk-ecdsa-sha2-nistp256@openssh.com,ssh-ed25519,ecdsa-sha2-nistp521,ecdsa-sha2-nistp384,ecdsa-sha2-nistp256,rsa-sha2-512,rsa-sha2-256,ssh-rsa,ssh-dss>
debug1: SSH2_MSG_SERVICE_ACCEPT received
debug1: Authentications that can continue: publickey
debug1: Next authentication method: publickey
debug1: Offering RSA public key: /home/MY_USER_NAME/.ssh/id_rsa
debug1: Server accepts key: pkalg rsa-sha2-512 blen 279
debug1: Authentications that can continue: publickey
debug1: Trying private key: /home/MY_USER_NAME/.ssh/id_dsa
debug1: Trying private key: /home/MY_USER_NAME/.ssh/id_ecdsa
debug1: Trying private key: /home/MY_USER_NAME/.ssh/id_ed25519
debug1: No more authentication methods to try.
Permission denied (publickey).

Update: I'm having the same problem with a different github account that has a different set of keys. Same computer.

Solution

So, I eventually figured it out. Turns out my computer just didn't like the fact that I had multiple ssh keys (possibly because one of them was password protected and others weren't?) Moving all but one of the ssh keys out from the ~/.ssh directory and restarting the computer solved my problem. I previously have tried removing all but one of the ssh keys but apparently a reboot was also needed.