Deployments to Heroku fail with error messages about Host key verification, saying that its not possible to read from the remote repository.
Often issues accessing private Github repositories will result in an error like this in your build log:
Host key verification Could not read from remote repository.
Why am I getting a host key verification error?
Heroku does not have the private keys necessary to access your private Github repositories, and as such, attempts to access those private repos will fail.
Use OAuth tokens
Rather than providing Heroku with the private keys necessary to access your Github repo, its much better to use OAuth tokens.
Accessing Github from automated tools, scripts, etc - such as builds on Heroku - is precisely why GitHub created tokens. You can read more about this here: https://help.github.com/articles/git-automation-with-oauth-tokens/