It is really hard to say what is going wrong here without seeing it but i still think that something is wrong with Security Rules, routing, ssh key pair or Internet Gateway.
Please review everything against our official guides.
i recommend that you destroy the environment and redeploy it and following this guide https://docs.paloaltonetworks.com/vm-series/9-0/vm-series-deployment/set-up-the-vm-series-firewall-o...
or use the following script https://github.com/wwce/aws-cft/tree/master/AWS-Ref-Architecture
Click Accept as Solution to acknowledge that the answer to your question has been provided.
The button appears next to the replies on topics you’ve started. The member who gave the solution and all future visitors to this topic will appreciate it!
These simple actions take just seconds of your time, but go a long way in showing appreciation for community members and the Live Community as a whole!
The Live Community thanks you for your participation!