Claro que é possível.
É provável que você só precise adicionar uma rota padrão à sua configuração de VPC, apontando para o ENI da sua instância do NAT.
A outra opção é associar um EIP à sua instância privada. Você não precisa criar nenhuma regra de grupo de segurança de entrada, mas um efeito colateral de atribuir um EIP é que a AWS lidará com qualquer tráfego de saída para você, com sua infraestrutura de NAT.