Where are our iCloud images stored?
The reason this seems confusing is that you've added the photos to "Shared albums".

Usually you would add your own photos to the Photos Library, which is essentially meant to be a collection of all your photos. Compared to that, "Shared Albums" is meant for taking out smaller collections of photos that you want to shared with third parties. 

Photos added to your own Photos Library do count against your iCloud storage limit, however photos added to shared albums do not. This is why you're not seeing any increase in your usage of iCloud. Shared albums comes with a built-in limitation of 5000 photos per album.

You can read more about iCloud Shared Albums storage restrictions here:

https://support.apple.com/en-us/HT202786

When you add a photo to a shared album, or to the Photos Library, the photos are uploaded to iCloud, yes. Whether or not they're also stored locally on your phone depends on your settings and how much storage space you have. You can choose to "Optimize storage", which means that only some is keps in full resolution on your phone, as space permits, otherwise only low res versions are kept on the device. The full res versions will be fetched from iCloud on request.

If you reinstall your phone, nothing happens to the iCloud stored photos. They will all be intact and ready to be synced after the phone is back up and running. However, note that you will need to be able to login with your Apple-ID (i.e. remember email-address, password and 2FA device if applicable).

Whether or not this is sufficient as a backup solution is up to you. If it were me, I wouldn't say it is sufficient - I would always keep photos stored in a minimum of two systems. With iCloud Photos you can setup your devices so that the full res images are stored both in iCloud and on a local device. This leaves you with 2 copies... however a single error (user error or bug) could erase your photos from both places at the same time. That's why I always recommend a second backup.