is it possible to replace the crystal on our 2k9's with something faster?
Practically, no. The arduino-specific code is written for 16MHz and 8MHz only.
Resonators tend to be cheaper, in part because they have built-in capacitors (component count goes from 3 to 1). As already noted resonators are less precise, and crystals tend to have wider operating temperature ranges.
-j