I upgraded the plugin from 1.39 to 1.56, and I ran into the problem described here: https://issues.jenkins.io/browse/JENKINS-62724

I did one of the suggested work-arounds, and set host key verification strategy to "accept-new". This fixed the problem and the master was able to connect to the worker. But then the launch process failed with this error:

[01/06/21 12:53:46] Launching agent
 $ ssh -o StrictHostKeyChecking=accept-new -i /tmp/ec2_3758075157863017322.pem jenkins@10.0.72.204 -p 22 java -jar /var/lib/jenkins//remoting.jar -workDir /var/lib/jenkins/
 command-line line 0: Bad yes/no/ask argument.
 ERROR: Unable to launch the agent for EC2 (us-east-1) - on-demand slave (i-07549b8eaad017d1e)
 java.io.EOFException: unexpected stream termination
 at hudson.remoting.ChannelBuilder.negotiate(ChannelBuilder.java:415)
 at hudson.remoting.ChannelBuilder.build(ChannelBuilder.java:360)
 at hudson.slaves.SlaveComputer.setChannel(SlaveComputer.java:419)
 at hudson.slaves.CommandLauncher.launch(CommandLauncher.java:165)
 at hudson.plugins.ec2.ssh.EC2UnixLauncher.launchScript(EC2UnixLauncher.java:256)
 at hudson.plugins.ec2.EC2ComputerLauncher.launch(EC2ComputerLauncher.java:48)
 at hudson.slaves.SlaveComputer.lambda$_connect$0(SlaveComputer.java:292)
 at jenkins.util.ContextResettingExecutorService$2.call(ContextResettingExecutorService.java:46)
 at jenkins.security.ImpersonatingExecutorService$2.call(ImpersonatingExecutorService.java:71)
 at java.util.concurrent.FutureTask.run(FutureTask.java:266)
 at java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1142)
 at java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:617)
 at java.lang.Thread.run(Thread.java:745)

I'm pretty sure that the "Bad yes/no/ask argument" is coming from the SSH command on the line above that, and indicates that the option "StrictHostKeyChecking=accept-new" is invalid. The docs for OpenSSH say that accepted values are "yes", "no", and "ask", so that makes sense; is there some other version of SSH that understands "accept-new"?

I changed the verification strategy to off, and that fixed it. Which obviously is not an acceptable long-term solution.