A chave é ter (pelo menos) um nó NAT em cada AZ.
O motivo: se um (ou mais) AZ estiver com problemas, você deseja que a conectividade de saída com a Internet seja funcional.
Você pode configurar um nó adicional para monitorar os outros ou fazer com que eles monitorem uns aos outros (embora haja uma pequena chance de que, sem um nó de monitoramento, você obtenha alguns falsos positivos).
Embora você possa usar grupos de escala automática, o AWS fornece um bom exemplo de nós verificando os outros por meio de um script simples, a escolha é sua no final do dia.