Whenever I tried to ssh from one of my Google Cloud VMs to another, I got an error message. SSH asks me if I want to continue connecting, and when I say "yes", I get: Permission denied (publickey). If I just type enter (fingerprint), I get Host key verification failed. Solution for both issues: # ssh -o "StrictHostKeyChecking no" thorsten@linuxintro.org A question that remains open with me is why I did not have to do it earlier. Earlier, the host keys were automatically added to the known_hosts file. Now I get the next error: # ssh thorsten@linuxintro.org thorsten@linuxintro.org: Permission denied (publickey). To resolve this error, I need a private/public ssh key pair on my laptop. If you don't have a public key, create it using the command ssh-keygen Type ENTER for every question from ssh-keygen. Then you will find your public key file in your home directory under .ssh/id_rsa.pub. Find out how it looks, here is mine: # cat .ssh/id_rsa.pub ssh-rsa AAAAB3NzaC1y...