I’ve always used GitHub’s directions here https://help.github.com/articles/generating-a-new-ssh-key-and-adding-it-to-the-ssh-agent/ with a blank password.
Adding your private key to https://circleci.com/gh/:org/:project/edit#ssh
as you have been doing is correct. https://circleci.com/docs/2.0/add-ssh-key/
Sine it doesn’t work directly with SSH I think it’s likely something with the key, since the others work correctly.
Can you also respond to the ticket with a build where the other keys worked, so I can see if there is something different about them? Or were those 1.0 builds?