I've been too afraid I might accidentally give some app permission to the contacts, or I would eventually have to use an app that forced me to give the permission.
I have some contacts in my password manager, but it is a bit cumbersome.
Are you afraid of your own device(s)?
What solutions or workarounds do you have in place?
Malware, vendor-ware and bugs lead to data leakage. If you are paranoid, you don't store contacts on your phone, nor make calls from your phone
Just use an old burner phone and write the numbers onto paper.