Since Heroku's documentation was incomplete I found some guidance from Github. Apparently I was not using my SSH Key https://help.github.com/articles/error-permission-denied-publickey#make-sure-you-have-a-key-and-ssh-is-using-it . Which I found out by running
ssh-add -l
I then added it by running
ssh-add ~/.ssh/[name_of_key]
So you just replace "[name_of_key]" with your filename (modify the path if you need to). And do not include the .pub
extension or you will get an WARNING: UNPROTECTED PRIVATE KEY FILE!
error.
You will then be prompted for your passphrase
Enter passphrase
And get a confirmation if all goes well
Identity added: