gcloud SSH connection asks for password instead of passphrase

Before doing the following please backup you ~/.ssh/config file. You may have a bad time if not.

This was solved by deleting the configuration done by gcloud with

gcloud compute config-ssh --remove

After that reinstalling the configuration running the same command as stated in the question:

gcloud compute config-ssh

This adds an alias for the instance to the user SSH configuration (~/.ssh/config) file and update the project SSH metadata.