Ok, então depois de muito vodu, eu consegui o sftp para Google Cloud VM trabalhando.
Você precisa gerar um par Public-Private Key em sua máquina local, você pode usar ferramentas como ssh-keygen (linux) ou putty-gen (windows).
Depois de ter o par de chaves, você pode ir para a seguinte janela no console da web do Google.
Console > Metadata > SSH Keys > Edit > Add Item > Here goes our public key
Agora, como sou muito fã do FileZilla, naveguei para a seguinte configuração e adicionei a chave privada.
Edit > Settings > Connection > SFTP > Add Key File
Agora, tenha em mente o "comentário-chave" gerado durante a criação ou talvez adicionado por você mais tarde será o nome de usuário do ftp e a senha será *blank* .
Feliz ftpeeing.