Heroku error: “Permission denied (public key)”

Try heroku keys:add <path-to-your-public-key>.

For example, heroku keys:add ~/.ssh/id_rsa.pub