Fisher-Yates++. There are modules to keep one from having to cargo-cult/copy-n-paste it often.

You'd think your early line more frequent argument would make sense, but if you look at perlfaq5 "How do I select a random line from a file?" the given algorythm is very similar. (Admittedly I can't really say either way, as when I've tried to adapt it to do this in the past I ended up with other anomalies.)

--
perl -pew "s/\b;([mnst])/'$1/g"