It’s not a required that a service provider is Privcay Shield-certified, only that they follow the EU/EEC laws and regulations.
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.