I'd like to solve the following problem using command line:

I'm trying to run the following PoC script from a GCE VM in project-a.

gcloud config set project project-b
gcloud compute instances create gce-vm-b --zone=us-west1-a
gcloud compute ssh --zone=us-west1-a gce-vm-b -- hostname

The VM is created successfully:

NAME ZONE MACHINE_TYPE PREEMPTIBLE INTERNAL_IP EXTERNAL_IP STATUS 
gce-vm-b us-west1-a n1-standard-16 10.12.34.56 12.34.56.78 RUNNING 

But get the following error when trying to SSH:

WARNING: The public SSH key file for gcloud does not exist. 
WARNING: The private SSH key file for gcloud does not exist. 
WARNING: You do not have an SSH key for gcloud. 
WARNING: SSH keygen will be executed to generate a key. 
Generating public/private rsa key pair. 
Your identification has been saved in /root/.ssh/google_compute_engine. 
Your public key has been saved in /root/.ssh/google_compute_engine.pub. 
The key fingerprint is: 
...
Updating project ssh metadata... 
.....................Updated [https://www.googleapis.com/compute/v1/projects/project-b]. 
>.done. 
>Waiting for SSH key to propagate. 
>ssh: connect to host 12.34.56.78 port 22: Connection timed out 
>ERROR: (gcloud.compute.ssh) Could not SSH into the instance. It is possible that your SSH key has not propagated to the instance yet. Try running this command again. If you still cannot connect, verify that the firewall and instance are set to accept ssh traffic. 

Running gcloud compute config-ssh hasn't changed anything in the error message. It's still ssh: connect to host 12.34.56.78 port 22: Connection timed out

I've tried adding a firewall rule to the project:

gcloud compute firewall-rules create default-allow-ssh --allow tcp:22 

.

Creating firewall... 
...........Created [https://www.googleapis.com/compute/v1/projects/project-b/global/firewalls/default-allow-ssh]. 
done. 
NAME NETWORK DIRECTION PRIORITY ALLOW DENY 
default-allow-ssh default INGRESS 1000 tcp:22

The error is now Permission denied (publickey).

gcloud compute ssh --zone=us-west1-a gce-vm-b -- hostname 

.

Pseudo-terminal will not be allocated because stdin is not a terminal. 
Warning: Permanently added 'compute.4123124124324242' (ECDSA) to the list of known hosts. 
Permission denied (publickey). 
ERROR: (gcloud.compute.ssh) [/usr/bin/ssh] exited with return code [255].

P.S. The project-a "VM" is a container run by Prow cluster (which is run by GKE).