It does seem a little like phishing; no personalization (name/account number), plus the included link (generally a no-no in these types of legit emails). But it's formatted pretty nicely, using their new brand identity. And I did log in by manually typing "southwest.com" so it does seem now to be verified as legit.

I agree that detection seems more sophisticated than one might expect from WN's IT. I suppose they keep track of failed login attempts, but it seems like the message generated by that kind of issue would be different. Most companies keep that message pretty straightforward. That's what leads me to think it may have been a mass breach… but if that were the case others should be seeing this notification as well.