There is no residency requirement to become a Cape Verdean citizen by marriage to a Cape Verdean. This is not termed "naturalization" in Cape Verde, even though it is by option. It is not automatic or immediate; the non-citizen must formally request it before they can be given citizenship, and they must request it after they are married. As seen on the Portondinosilha page for acquiring citizenship, there are 5 groups of persons who may acquire Cape Verdean citizenship, further organized into 3 categories:
- Children or grandchildren of Cape Verdeans ("by origin")
- Foreigners married to Cape Verdeans ("by marriage")
- Foreigners who wish to become Cape Verdeans by their own will ("by naturalization")
The 5 year residency requirement you saw is for acquiring citizenship via naturalization, not via marriage.
That page has a list of the documents required. The foreign spouse needs criminal records from their country of origin and of residence. Note that if the foreign spouse is male, they need to present documentation of their military service, or exemption from military service, for their country of citizenship. If they're from a country without mandatory military service and didn't serve, bring whatever documentation you can.
I don't have statistics on how long it takes to acquire citizenship via marriage. I went through the process myself about 5 years ago. Once I had sorted out what documents they needed and turned them in, I found myself going back to the Registry Office over and over again, just to get told "nope, not ready yet, come back next week." Parts of the process required the signature of the Director of the Registry, who was sometimes traveling. I learned very well to double check all documents you receive in Cape Verde for mistakes, even after corrections have been made.
Visa exemption, even without citizenship
At least one of the benefits of citizenship is granted without actual citizenship: according to the Ministério das Comunidades, a foreigner is allowed to enter Cape Verde without a visa if they are married to someone who was born in Cape Verde. You must bring appropriate documents with you to present at the border. I have heard of someone who had to argue their case because the border control officer was not aware of this law.