I think the fediverse does have a privacy problem, however as long as your account can’t be linked to you (malicious instance, your email being breached) it doesn’t matter all that much (at least for my threat level) because the info is confined to the fediverse, where little can be done with it, especially if you swap instances/accounts commonly. Yes, one could create a profile on you based on what you upvote/downvote, but they can’t for example use that to serve targeted ads, because the fediverse doesn’t have a ad network and when visiting other sites they can’t associate your profile with you (assuming you don’t reuse your username), unless I am forgetting something.
tldr: The fediverse isn’t private, but the data is practically useless
Just fyi https://inv.nadeko.net/ somehow still works. Also there is stuff like freetube/libretube. As for search engines, I assume you have mullvad vpn, you could use mullvad Leta (don’t know how good they are right now, haven’t used them in a while). Also there is Swisscows