The public keys are stored on the server (by necessity) but not the private keys. The actual connection is directly between two of your own machines, or routed through a DERP server (encrypted end-to-end) in rare cases.

But if you’re concerned, you can instead self host headscale or netbird.

That makes zero sense. Where did you get that idea from?

For reference, here are their docs describing key management. https://tailscale.com/blog/tailscale-key-management