GitHub’s implementation of git over ssh identifies accounts (for purposes of access control) solely by ssh public key. As a consequence, a particular public key can be associated with, at most, one account. Deploy keys are even more restricted - they can only be associated with a single repository. While ssh can try several keys, GitHub doesn’t know what you’re trying to access until after you authenticate, so a workaround is required to select the right key.

When I ran into this problem, my solution was to add a little magic to my ~/.ssh/config

1# apply these config options to matching hosts
2Host *.github.com
3# don't attempt to use keys from ssh-agent
4# unless they are explicitly listed here
5IdentitiesOnly yes
6# this specifies which key to use - %h
7# will be expanded to the hostname
8IdentityFile ~/.ssh/%h_id_rsa
9# for purposes of server verification,
10# pretend the hostname is github.com
11HostKeyAlias github.com
12# since the hostname provided is wrong
13# we use netcat as a proxy to ignore it
14# and connect to github.com anyway
15ProxyCommand nc github.com 22

The trick here is the “%h” expansion in the IdentityFile parameter, which makes this single config block work for as many users and deploy keys as you like. Once this is in place, you can use ssh-keygen -b 2048 -t rsa -f ~/.ssh/IDENTIFIER.github.com_id_rsa to create a new keyfile, where “IDENTIFIER” is your username, or in the case of a deploy key, the repository name (really, it can be anything, but having a naming scheme avoids confusion later). Then, when cloning or setting remotes, you’ll use “IDENTIFIER.github.com” instead of just “github.com”.

Once you have the public key added on GitHub, you can test that the key is working:

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

This will probably work on other services that use git over ssh, but I’ve only tested it on GitHub.