A contact stored in iCloud takes literally next to 'zero' storage space. Instead of guessing and messing with deleting individual stored contacts to reduce your iCloud storage, you should really try to check other things:
Go to iPhone Settings app > tap your account (first item on top) > tap iCloud, tap Storage (again first item). On this screen, you can see what exactly is taking up your space on iCloud. It's also the place where you can manage (and delete) each individual category that's being stored. So again, actually everything that is being stored is listed here, also data from individual apps. It's sorted by occupied space, so now it should be easy for you to see what's the problem.