i had the same case on linux ubuntu and just fixed it, it seems that OS was confused between the /root/.ssh/ and home/user/.ssh/ dir, what i did was:
heroku keys
heroku keys:clear
heroku keys:add
now in here if heroku couldn't find a key and asked to generate one right no, and this mean you have the same issue as mine, do the add command like this heroku keys:add /root/.ssh/id_rsa.pub
the path that you'll add will be the one that you got in step 2.git push heroku master
now