I used Google before, but since I degoogled, I only have my contacts on my Android phone. However, I would like to be able to access them on Linux too and have them synced.
I run a Nextcloud server and use DavX5 on my phone to sync my contacts and calendars over WebDAV. Works great.
If Nextcloud is more than you need, you might try Radicale which just does CalDAV and CardDAV.
Use a service with card DAV support like https://posteo.de.
My contacts are synced between an iPhone, Linux Mint and a Mac. My Parter syncs between an iPhone and a Windows PC (Witt Thunderbird as mail Client).
I use fossify contacts, which allows you to read and write your contacts to/from a VCF file (as opposed to import/export which must be manually done, this keeps them in the file so as you add/remove contacts the file is updated) and synchthing to keep the VCF file synced between my devices. No servers of any of that maintenance overhead needed.
You can use synchthing for all kinds of stuff too. I sync calendar (with fossify calendar) and a keepass PW database and 2fa keys this way.
I’ve tried everything else. DavX, caldav and carddav, running a little server for all this stuff, it’s all fine but it requires you to maintain a server which is your canonical backup. I decided to ditch all that extra stuff and just go with syncthing and files.
Well, I use NextCloud (via Nextcloud AIO) as my cloud backend for almost everything. If all you want is contact syncing, that is almost certainly overkill. It’s a Big project that does just about everything.
If I remember correctly, there were a few more focused projects listed in the Awesome-Selfhosted repo that may be useful to you.
I hoy Baikal.myself and sync to it via davx5 on android and via Thunderbird in ubuntu