If you've already uploaded the key then try to remove the key and then re-upload it with a new key.
heroku keys:remove //removes the existing key
ssh-keygen -t rsa //generates a new key in ~/.ssh folder
heroku keys:add //uploads the new key, if no arguments r passed then the key generated
//in default directroy i.e., ~/.ssh/id_rsa is uploaded
git push heroku
this should work.