Acontece que a documentação que ajudou foi:
[EC2-VPC] Verifique a tabela de rotas para a sub-rede. Você precisa de uma rota que envie todo o tráfego destinado para fora do VPC (0.0.0.0/0) para o gateway da Internet para o VPC.
EC2 Solução de problemasInstalaçõesConectando
Eu adicionei a rota e consegui acessar o SSH na instância.