Basta substituir ~/.ssh/google_compute_engine pela nova chave e usar gcloud compute ssh normalmente para obter acesso às suas instâncias de VMs; a chave será automaticamente propagada para as instâncias que ainda não a possuem.
Se você quiser remover as chaves anteriores, remova-as dos metadados de todos os instâncias em que pode ter sido usado; a entrada attribute/sshKeys possui uma lista de chaves ssh. Consulte os documentos para metadados padrão para obter mais informações.
Consulte os documentos para Como configurar metadados personalizados para saber como você pode usar gcloud para alterações de script para metadados de todo o projeto ou de instância de VM.