Um Gateway NAT (bem como uma Instância NAT, pelo que vale a pena) deve estar em uma sub-rede pública porque somente dispositivos em sub-redes públicas podem realmente usar um endereço IP público.
Isso é o que faz de uma sub-rede pública uma sub-rede pública.
A definição pedante de uma sub-rede pública é uma sub-rede cuja tabela de rotas VPC associada tem pelo menos uma rota apontando para o Gateway de Internet ... mas na prática, normalmente é uma sub-rede com sua rota padrão (na tabela de rotas VPC) apontando para o gateway da Internet.
Por outro lado, uma sub-rede privada é uma sub-rede sem essa rota. Normalmente, a rota padrão para uma sub-rede privada aponta para um dispositivo NAT, embora possa apontar para uma VPN de hardware ou uma conexão de conexão direta.
Se um dispositivo NAT não estiver em uma sub-rede pública, ele (por definição) não tem rotas pelas quais o tráfego traduzido pode alcançar a Internet, porque seu tráfego de saída segue a tabela de rotas para a sub-rede na qual está localizada ... então a sub-rede em que o NAT Gateway está localizado - novamente, por definição - deve ser uma sub-rede pública.
Não há implicação de segurança de colocar um NAT Gateway em uma sub-rede pública, já que as tentativas de conexão de entrada nunca são aceitas em nenhuma circunstância. Isso é algo que você não pode desconfigurar.
Se você está pensando em termos de LAN, a suposição natural é que um dispositivo NAT precisa estar "ligado" a pelo menos duas sub-redes, a sub-rede externa (endereços públicos) e a sub-rede interna (endereços privados). A rede VPC não é a LAN que parece ser. É uma rede de camada 3 definida por software que emula Ethernet de maneira muito clara, mas não é Ethernet.