Authentication through knowledge of a SSN is an absurd practice, and is a non problem in countries which have a national ID card scheme. Introducing ID cards would be my obvious response to this leak. Not re-issuing SSN until the next major leak.
Having a universal unique identifier for every individual across systems is a different matter and I am not convinced this is even desirable. In a world where no organisation is able to protect its data (or even willing since most organisations now are looking for ways to monetize it), this is making it too easy to link an identity across breaches. I don't think your utility companies have any need to know your SSN.