How to change SSH key on Google Cloud?

Just replace ~/.ssh/google_compute_engine with the new key and use gcloud compute ssh as you normally would to get access to your VM instances; the key will be automatically propagated to the instances that don't already have it.

If you want to remove the previous key(s), remove them from the metadata for all of the instances where it might have been used; the entry attribute/sshKeys has a list of ssh keys. See the docs for Default metadata for more info.

See the docs for Setting custom metadata for how you can use gcloud to script changes to either project-wide or per-VM-instance metadata.