"Repository Not Found" when accessing a GitHub remote

Boy was this frustrating! Basically I have several keys in ~/.ssh/ that I use to access various projects. It turned out that one of them was added to GitHub on another account (likely a bot account I had created for another project).

I would try to run a git pull but would be greeted with an error:

$ git pull
ERROR: Repository not found.
fatal: Could not read from remote repository.

Please make sure you have the correct access rights
and the repository exists.

This would only happen on my org-owned projects, since my personal projects worked just fine. So what was the issue?

We get a hint by following the troubleshooting tips here: https://docs.github.com/en/free-pro-team@latest/github/creating-cloning-and-archiving-repositories/error-repository-not-found

$ ssh -T git@github.com
Hi <not my expected username>! You've successfully authenticated, but GitHub does not provide shell access.

Basically my SSH agent (gnome-keyring) was presenting a key that belonged to a valid GitHub user (so authentication passed), but not one with access to my project (so GitHub denied access).

In other words, even though I had the correct key in my keychain, the SSH agent presented the wrong one, so I couldn't access the repository.

The solution: add this to my ~/.ssh/config:

Host github.com
    IdentityFile /path/to/the/correct/key

Now when I perform a git pull it authenticates correctly:

$ git pull
Already up to date.