Nothing on your phone is completely private
One of the things that struck me while reading about Google shutting down a customer account is that nobody is shocked that Google regularly scans the photos on your phone.
It's not easy to grasp that every interaction with a service–mail, message, browsing...–finally leaves a trace somewhere in a cloud. It works so transparently and conveniently, that we are shocked a how many things don't work anymore whenever we temporarily lose access to the internet. The other face of this convenience is that our data trail is algorithmically processed and accessed in more than one way.
There is no easy solution to this. For example, even if you changed your email provider to a company in Switzerland, you'll still depend on Google or Apple for your phone to work reasonably well[^android-google-free]. Even message services with end-to-end may hold the key to decrypt your data if needed.
A rule of thumb I follow: don't consider anything in your phone completely private.
[^android-google-free]: There are ways to use your Android phone 'Google free', but it comes at a price. That price is reduced app availability, increased technical complexity, and finally no one guarantees you who is behind those 'Google free' versions of Android.