Out-of-band means you need to transfer (or at verify) the ssh host key over something other than ssh for the initial connection. The host key is how the client verifies the server is who it says it is. The client caches the key after the initial connection. But for that initial connection, there's no way to know that the key isn't that of a MITM attacker.

One way to get the key out of band might be from the AWS console for example. Presumably that connection is protected via HTTPS where the CA infrastructure (theoretically) can protect against MITM attacks.

BTW, it's also possible to setup ssh to use certificates instead of simple keys which might make sense depending upon how many hosts you manage.