I fell on ice last year and immediately bought new boots. I highly recommend Keens and some microspikes like others have mentioned.

Look up frostbite info. Read the weather warnings on your phone daily, they will indicate how long before frostbite sets into uncovered skin. Sometimes it's as little as 15 minutes.