Right. What about paid service. Shall I pay with someone else's CC or ask the bank for another one just because I don't want to be tracked.

Many banks and credit card companies offer a service that lets you generate a one-time-use credit card number.

But your billing address will still be the same

So what?

Paid services necessarily require a higher level of trust (since you are handing them money) than random internet services. So we are off-topic from ssh keys and identity.

If you don't want someone knowing your personal payment details (CC #, billing address), then pay in cash and use services don't deliver things to your home. And if you can't, then just don't use a service.

But that's living in way too much paranoia for most of us.