As a RSA-user myself, because I learnt about ssh through the github setup guides: Will ssh-keygen generate a secure key if I don’t pass it any parameters?
You need recent ssh-keygen's -o to make the passphprase effective (default for ed25519). That was covered here at some stage, but I don't have a reference.
They don’t need to. Boot up a default AMI, change the key to whatever you want, then create your own custom AMI from that. Or you can use something like Cloud-Init.