I wouldn't drive it with 25KHz neither, mainly for the said edd currents, they're usually solid iron (not ferrite), won't be happy at KHz range, but anyways it would be overkill.
100-200Hz should be good enough, most cars drive their solenoids at similar frequencies.
The back-EMF diode will also make it turn off slower (The current keeps circulating for a small time)