No, you should do it via SSH, just try to do it as soon after standing up your server as possible.

The only place I know of that gets this right is Amazon, who stands it up with a key (admittedly one of theirs) that they force you to download before you can connect the first time.