Yep Strato totally sucks.
I used to recommend Netcup, but I stopped doing so after some very strange performance issues likely due to over-provisioning. But depending what you want to use it for it might not matter so much and the low prices are more important. There is also Contabo, but probably the same applies to them as Netcup.
Maybe look into Hetzner. I only have second hand knowledge about them, but I never really heard anything bad.
OVH is also ok... after their recent big fire they probably have the cheapest backups and very new hardware 😅
But have you considered self-hosting from home? It's quite fun to do and most stuff works just as well on a reasonably fast internet connection.