I think removing this altogether is a bad idea. In my opinion there's very little that's private about when someone's last been seen on the site, although since that doesn't seem to be a universal opinion (given the voting here) I'd suggest just reducing the precision, and maybe what's counted as being "seen".
First, reducing precision. The main use for the last seen indicator is with comments, bounties, and similar actions where knowing how active a user is is important. If an answer's invalid, for example, it doesn't make sense to leave a comment about it if the answerer hasn't been seen in a decade. If they were last online yesterday though, instantly flagging the answer is also the wrong choice.
Second, changing what counts as being seen. I personally disagree with this, since there are quite a few users who check the site regularly but don't actively ask or answer much. However, changing it from passively viewing the site to things like checking an inbox notification or voting could help with the privacy aspect a bit.
Personally, I think reducing the precision would have very little impact on the feature's usefulness for moderation purposes, but would remove a lot of the privacy issues with it. I disagree with changing what counts as being seen, and just changing the precision is almost certainly enough. But please, don't remove this feature. This isn't a social network, it's a Q&A site, and there are multiple legitimate uses for knowing how active someone is.