It’s not a required that a service provider is Privcay Shield-certified, only that they follow the EU/EEC laws and regulations.
You can be compliant by having a privacy policy available on your website detailing how you collect personal information, what information you collect, why you collect it and how you use it. Of course, you must also actually treat the information you collect and store according to the laws (and your privcacy policy).
However, in order for you (or your company) to be compliant, your vendors must also be compliant. If they are not Privacy Shield-certified, you must have a (written) agreement with the provider that they will treat the data you store with them in compliance with the EU/EEC privacy laws. For example, Linode is not certified, but they do offer a custom EU contract for customers who ask for it.
Regardless of GDPR, if you are collecting and storing any personal information from EU/EEC citizens, you already need to be compliant with the EU/EEC laws. For example, if you are logging the IP addresses of your website visitors, this is considered personal information by the EU.
Side note
Unfortunately, I had to read up on these laws recently as I realized I had to create a complete privacy policy for my (static) web site simply because I had a contact form and my web server was logging IP addresses, and when GDPR hits, I actually have to add a “I accept that you collect and store this information according to your privacy policy” check-box on my contact form (which can not be checked by default).