Okay, I've not used that before (you learn something new every day
)
How will you authenticate to each server to allow it to install your public SSH key? You will probably have to provide a password, after all you wouldn't want just anyone connecting and setting themselves up with a public key to login as root now, would you?
That may prove a bigger headache than responding to the prompts. Is there a privileged account that is already able to connect to each server? You should then be able to force out the new public key (making sure you get the permissions correct) through that.
Sadly, hindsight is a wonderful thing.
Robin