I had the same problem, I followed this post and others of the same kind without success :-((
Finally, I found the solution:
I had to add my new rsa identity in my machine!
So, first of all I created a new rsa key:
ssh-keygen -t rsa -C "giordano.scalzo[at]gmail.com" -f ~/.ssh/id_rsa_heroku
then added it to my machine
ssh-add ~/.ssh/id_rsa_heroku
and, finally, to Heroku
heroku keys:add ~/.ssh/id_rsa_heroku.pub
After that,
git push heroku master
worked like a charm!
Hope this helps.