Como você disse. A resposta para o seu SSH de saída será da porta 22 e não para a porta 22, mas para a porta aleatória que foi escolhida com a conexão de saída inicial. Portanto, nenhuma regra será igual. E suponho que você tenha uma política padrão de DROP, caso contrário não haveria essa pergunta.
Basta adicionar a mesma regra à cadeia OUTPUT:
iptables -A OUTPUT -m conntrack --ctstate ESTABLISHED,RELATED -j ACCEPT
Essa é a regra que transforma o firewall "stateful" usando o conntrack para permitir automaticamente o fluxo reverso.