SSL certificates with password encrypted key at hosting provider

Whatever happens, you'll need to decrypt the keyfile in order to use it. There are a few options.

1. Decrypt the keyfile and use that. This offers permanent graceful restart of your services which is what you are after. But the key then is unprotected, unencrypted stored on your server.
2. Give the service provider passwords to your certificates. This might be ideal however you need a level of guarantee that the service will be restarted with the prompt on startup. Be that they may have their monitoring software alert them for this event, however you should under these circumstances be open to situations where the key password is not entered, either at all or with a delay in the password being entered by the service provider. It will be down to you to negotiate what terms the service provider will offer you this service and what guarantees of success they will provide. If they will provide it at all.
3. Some http servers, such as apache provide a option called SSLPassPhraseDialog which will attempt to decrypt the key using an written program that will pass the correct passphrase out when executed. This can be a shell script or program of your choosing that will do this. This has the benefit of giving you option no 1, but acts merely as a weak barrier to all the problems described in option number 1. In addition, depending how careful you are (or not) supplying a password executable this might provide a mechanism for someone to get something other than the passphrase executable to run at startup.
4. Have your hosting provider require they supply with with a scheduled downtime (if its them doing the rebooting) so you can be ready to insert the password in yourself, or alter the updates to run at time where you can be ready to enter the pass phrase to the certificate promptly.

My first suggestion is ask yourself why you need to encrypt the SSL certificate for, and what losses this produces on your operation if service is down for, say - 2 hours until it is discovered. What are the potential losses to you if the certificate is breached, and how much time would it take to rectify? If it costs more than your SSL certificate itself and the time to recover in the event of a breach is too high, then perhaps it is right to keep it encrypted.

To be blunt, you cant have your cake and eat it. If you want to encrypt the SSL key, then you do so at the cost of non-graceful restarts and delays to your operation. If you encrypt it but provide a way to automate decryption, its probably just as worthless, or potentially more dangerous than having the key decrypted in the first place. If you make it your VPS providers responsibility, then your just shifting the problem onto them and it will likely either cost you a lot to give you the guarantees you want, or you'll have to accept that there will be times where the VPS provider doesnt meet your expectations when they reboot the VPS.

My suggestion, is to make reboots timely and with forewarning, I dont think it would be unreasonable to ask your VPS provider for this. That way there shouldn't be an incident you cannot at least put under some control.

*The problem of using SSLPassPhraseDialog is a similar, more common and problematic mistake people do with cron jobs. That is, deploy cronjob to run as root, then make the files ownership of whats run a non-root (say FTP) user who can potentially modify the application to escalate privileges. If you write a program to spit out the passphrase, make steps to ensure that the file is not readily readable nor is the file modifyable with anything but root (this includes making sure its parent directory its kept in is not owned by someone else).