Github SSH Permission denied to deploy key

For me the following always works for GitHub push:

eval `ssh-agent -s`; ssh-add your_key; git push

You mentioned you were using OSX. If you're on 10.12.2+ it may be a problem with your ssh config. Github's documentation has a note about that.

https://help.github.com/articles/generating-a-new-ssh-key-and-adding-it-to-the-ssh-agent/

Specifically they say add the following to ~/.ssh/config

Host * AddKeysToAgent yes UseKeychain yes IdentityFile ~/.ssh/id_rsa

Hope this helps