It leads me to believe that there is either a shear pin, or key or some such that holds the gear retaining nuts in place. I think he just replaced 5th with the same gear, but the procedure would be the same whether or not the ratio was changed.
BTW, I refreshed my memory and the F5M is the earlier of the F-series transmissions, while the F25M is the latter version. According to the second link, it doesn't seem to depend on the engine being SOHC, or DOHC. Also the A26M-R is a manual even though there is an 'A' in the name.
The A26M-R might just work in your Protege5 MazdaMatt, IIRC the MS-Protege was a '03 model year, so that would be good for you. I'd sure love to shoehorn that critter into my MX-3 though!