O detalhe crítico é que a página que você mencionou é sobre como criar uma nova imagem de máquina do Compute Engine. Especificamente, quando você cria uma nova imagem de máquina virtual, deseja garantir que ela NÃO inclua nenhuma chave de host. Dessa forma, quando a imagem é clonada e reconstituída em uma VM real, o script de inicialização do sshd reconhece que não há chaves de host e gera automaticamente novas chaves. Isso é desejável porque ter várias máquinas usando a mesma chave de host é uma idéia muito ruim.
Portanto, no caso geral, por favor, não vá apagar suas chaves de host, mas se você estiver criando uma nova imagem, é um passo importante para garantir que haja uma relação de um-para-um entre as máquinas e chaves de host.