Depois de algumas pesquisas, parece que o Google Cloud Platform está com bugs quando se trata de aplicar chaves SSH às nossas caixas do Debian. Adicionando as chaves globalmente em um nível de projeto, ou adicionando usuários manualmente à caixa Debian, adicionando chaves manualmente a authorized_keys para cada usuário, ele funciona. Adicioná-los em um nível de instância não funciona. Eu vou reportar o bug para o Google.