High availability Bastion host - Best practices, ELB, EIP?

It looks like the requirement is to provide bastion functionality at lowest reasonable cost with an RTO of say 5 minutes. No RPO is applicable as it's effectively a stateless proxy that can be rebuilt easily.

I'd have a bastion host, defined either as an AMI or CloudFormation script (AMI is faster), inside an autoscaling group with min/max/target set to 1. I wouldn't have a load balancer as there's no need for that as far as I can see. This instance would be registered with Route53 with a public domain name so even if the instance changes you will be able to access it, and that should eliminate SSH warnings. I might start with one instance in each subnet, but I'd probably turn one off if they're reliable enough - they should be.

A CloudFormation deployment of bastion hosts is described by Amazon here. Amazon have a best practice guide here. You shouldn't address internal resources using their Elastic IP as they're public IPs and traffic to them is charged, whereas private IP traffic isn't charged. Domain names are cheaper. This might involve some CloudFormation script tweaking.