A magnet-coil (variable reluctor) or Hall effect (semiconductor sensor with amplifier) can detect the passage of a steel tooth. The reluctor will give a pulse (for each tooth) of a constant
number of volt-seconds, so the signal gets smaller at low RPM.
A Hall sensor will give a pulse proportional to field strength,
so the voltage is near constant (and if the amplifier has hysteresis, is of logic character).
Nonmagnetic metal will be problematic at low RPMs; steel
will give a better signal, unless the teeth are large compared
with skin depth of the material at the frequency of interest;
the depicted 16-tooth item, at 800 RPM, will give
about 200 Hz, so (for aluminum) greater than 6mm. You'd
also want the magnet field reach to be greater than 6mm.
A counter/timer software can compute
RPM from this, and if you use a digital sensor, it will
not require any amplification to drive the Arduino I/O pin.
Mainly, there will be need to position the sensor and affix
the gear to the shaft so that the signal has a margin
sufficient to always trigger when a tooth passes; too close,
and it could detect the entire shaft, and stay ON. Too
far away, it could fail to detect a tooth.
Age and temperature and mechanical wear will alter the
signal slightly, so a bit of position experimentation is called for; you might want to get a sensor in a machine-bolt form, so its position can be easily adjusted, in a fixture with a threaded bore. That's convenient, but expensive in off-the-shelf hardware. Optical lamp/sensor assemblies and striped or
perforated targets are an alternative.