Build fails with "host key verification failed" while installing node_modules

Question

UPDATE Clearing my build cache and deploying with no package-lock.json at all fixed.

Deploying my Node app to Heroku has started failing with Host key verification failed at installation of one of my dependencies, a public repository:

-----> Monorepo app detected
      Copied /server to root of app successfully
-----> Node.js app detected
       
-----> Creating runtime environment
       
       NPM_CONFIG_LOGLEVEL=error
       NODE_ENV=DEVELOPMENT
       NODE_MODULES_CACHE=true
       NODE_VERBOSE=false
       
-----> Installing binaries
       engines.node (package.json):  10.x
       engines.npm (package.json):   unspecified (use default)
       
       Resolving node version 10.x...
       Downloading and installing node 10.22.1...
       Using default npm version: 6.14.6
       
-----> Restoring cache
       - node_modules
       
-----> Installing dependencies
       Installing node modules
       npm ERR! Error while executing:
       npm ERR! /usr/bin/git ls-remote -h -t ssh://[email protected]/ethereumjs/ethereumjs-abi.git
       npm ERR! 
       npm ERR! Host key verification failed.
       npm ERR! fatal: Could not read from remote repository.
       npm ERR! 
       npm ERR! Please make sure you have the correct access rights
       npm ERR! and the repository exists.
       npm ERR! 
       npm ERR! exited with error code: 128
       
       npm ERR! A complete log of this run can be found in:
       npm ERR!     /tmp/npmcache.RchR7/_logs/2020-10-25T17_11_28_328Z-debug.log
-----> Build failed

There's been no change to my buildpacks, which were working before:

1. https://github.com/lstoll/heroku-buildpack-monorepo
2. https://github.com/heroku/heroku-buildpack-nodejs

• App has been running on Heroku for weeks, using the packages that ethereumjs-abi is a dependency of. (It isn't a direct dependency of my app.)
• ethereumjs-abi hasn't updated since I started using it
• App still runs correctly locally
• My own repo is private, but the package repo is public.
• I changed my SSH keys recently, but since adding them to GitHub haven't had any other SSH issues. I've now added the new key to Heroku with heroku keys:add and it had no effect.
• Previously I was specifying engines: { node: 10.x }, but have now also tried 12.x and 14.x
• Pushing from local master to Heroku master

Answer 1

Yeah a few days wasted so far...

Faced with the same issue when replaced npm package with my own fork and provided custom link on github.com.

What helped:

1. remove package-lock from GIT
2. clear cache with heroku builds:cache:purge --app $HEROKU_APP_NAME --confirm $HEROKU_APP_NAME