De acordo com esta resposta e esta diretriz
Eu precisava adicionar o key_pair.pem
ao agente ssh do OSX da seguinte forma:
ssh-add -K /path/to/key_pair.pem
(no meu caso, não pedi uma senha)
Depois disso, tudo funcionou bem usando as duas metodologias descritas acima.
Então, para responder à pergunta:
Q: Do I have to use ssh-agent on Mac OS X to log in to a private subnet instance through a NAT/bastion host?
A: YES