Heroku Upload - Permission Denied

I ran into a bit of trouble uploading an app to heroku for the first time, I was unable to authenticate.

root@chris-VirtualBox:~/site# git push heroku master
Permission denied (publickey).
fatal: The remote end hung up unexpectedly

This turned out to be an issue with my public key, in order to fix it simply create a new one:

root@chris-VirtualBox:~/site# ssh-keygen -t rsa
Generating public/private rsa key pair.
Enter file in which to save the key (/root/.ssh/id_rsa): 
Enter passphrase (empty for no passphrase): 
Enter same passphrase again: 
...

Re-upload it:

root@chris-VirtualBox:~/site# heroku keys:add /root/.ssh/id_rsa.pub
Uploading ssh public key /root/.ssh/id_rsa.pub

And finally re-push everything:

root@chris-VirtualBox:~/site# git push heroku master
Enter passphrase for key '/root/.ssh/id_rsa': 
Counting objects: 579, done.
Compressing objects: 100% (513/513), done.
Writing objects: 100% (579/579), 6.09 MiB | 83 KiB/s, done.
Total 579 (delta 101), reused 0 (delta 0)

-----> Heroku receiving push
-----> Ruby/Rails app detected

This Heroku page actually provides quite a bit of info if you’re still having problems: http://devcenter.heroku.com/articles/rails3