TL;DR; It will work, but it will be slow. Probably no more than 200kHz data rate.
\$R_{ds(on)}\$ is irrelevant in this circuit to be honest.
The channel resistance essentially acts as a potential divider with R4 or R3 when the output is pulled low. So even if it were 100Ω the output low voltage would still be no more than 100mV.
A larger on-resistance will slow down the falling edge slightly, but given the rising edge is entirely driven by the pull-up resistor anyway, the level shifter is no good for high-speed circuits (a few MHz tops depending on trace length and capacitive load).
Any MOSFET with a \$V_{gs(th)}\$ of less than \$V_{LV} - V_{sd}\$ (low voltage supply minus body diode forward voltage) should suffice for the circuit to work at some frequency, AO3400A meets that requirement.
However, as @SpehroPefhany points out, this is not the full story. As already mentioned, these circuits are slow, in part due to the pull-up resistors, but also due to the capacitance of the MOSFET, its \$C_{iss}\$ and \$C_{oss}\$ ("input" and "output" capacitances).
MOSFETs have capacitances between each of the terminals, which can be considered as capacitors between gate and source (\$C_{iss}\$), and between drain and source (\$C_{oss}\$). These capacitors will also act to slow the circuit down. The higher the capacitance, the slower the circuit.
The capacitance has the biggest impact in down-shifting on both rising and falling edges. For up-shifting the effect is minimised on the rising edge as C_{iss} helps give a boost, however the falling edge is affected just as much as the down-shifting mode.
Your chosen MOSFET has very high capacitance, which will limit the speed of the circuit. As a very quick approximate simulation, this shows the circuit in operation at 2MHz for both the BSS138 and the AO3400A. A screenshot of the results is shown below in case the URL breaks.
As expected, the AO3400A performs badly at this frequency. In fact slowing down the frequency from the simulation we can see for down-shifting about a 800ns rise time (10% to 80% Vdd) and about 50ns fall time. This compares to only a 40ns rise time for the BSS138.
You can probably get ~200kHz using the proposed transistor vs. ~4MHz with the BSS138.
How it works
I'll add a bit about how the circuit works for completeness. There are two modes of operation, up-shifting (LV1 is input, HV1 is output), and down-shifting (HV1 is input, LV1 is output).
For simplicity of the explanation, I'll assume that LV is 3.3V, and HV is 5V. The list numbers correspond to the number on the diagram at the bottom of the answer.
Up-Shifting (LV1 = Input, HV1 = Output)
Up-shifting is the easiest to understand.
When the input pin is high, then the \$V_{gs}\$ of the MOSFET will be zero - both the gate and source are at 3.3V. As such the MOSFET is turned off, and the output pin will be pulled up to 5V by R4.
When the input is pulled low, the source will be at 0V, but the gate will remain at 3.3V. As such \$V_{gs}\$ is now 3.3V and the MOSFET turns on. The MOSFET will pull the drain down to the source voltage (0V), which means the output pin will now be low. (The input pin is sinking current from both R3 and R4).
Down-Shifting (LV1 = Output, HV1 = Input)
Down shifting is a little more complicated.
When the input pin is high, there is nothing in the circuit pulling the output down. As such it will be pulled up to 3.3V by R3. This will make the \$V_{gs}\$ of the MOSFET zero, preventing any current flowing from input to output. As such the output voltage cannot exceed 3.3V, even though the input is 5V.
When the input is pulled low, the body diode of the MOSFET which goes from source to drain will start conducting and pull the output down. As the output is pulled down, the source voltage moves towards \$V_{sd}\$ (body diode forward voltage).
As this happens, \$V_{gs}\$ will now be \$3.3V - V_{sd}\$, which must be sufficient to turn the MOSFET on. Once the MOSFET turns on, the output voltage will then drop towards zero as the current through R3 flows through the channel rather than the body diode.
