I am big into self-hosting and would be happy to run my own Headscale server (I have actually) but imo it's not worth the effort.

It can be done but it requires a lot of effort and consideration to ensure the relays and routing work for when your clients are in challenging NAT scenarios. And the user experience is not as good.

Instead what I do is continue to use Tailscale but I use the Tailnet Lock feature to give signing authority to my own specified devices so any new devices must be signed off by one of those other devices.

This effectively eliminates the last point of trust where you had to trust tailscale's servers to manage authorization. The result is you don't have to worry about trusting tailscale at all, the entire system is zero trust.

The catch is if you lose those devices and the recovery keys you lose the ability to trust or add to your tailnet and your only real option is to delete all the devices and start fresh.

They also have the option to send a recovery key to their servers when you enable Tailnet Lock so support can rescue you in that scenario, but I think if you are using this feature on the first place it's because you don't want to do that so I imagine most choose not to lol

I linked to their blog post above because I think it explains the feature well. If you just want the docs they are here