The best option investigated was to use an SSH CA that is authorized across the fleet, create and sign a short-lived certificate for each interaction. This solution has been tested and works fine, but depends on upstream openssh accepting a patch, see the upstream bug and the PR on GitHub. The Puppet code and a small script to generate signed keys on demand from Python are ready to be used if/when the patch will be accepted upstream.

For now a normal SSH key armed with keyholder and with limited authorization on the target hosts will be used instead to not be blocked by this.
Resolving it for now.