Information-theoretic bound on leakage by timing measurement
As you say, if the measurements are accurate then the device can leak $log_2(n)$ bits of information on each invocation.  If it lacks internal storage then it can't track which parts of the key it has already leaked.  What it can do is leak a random set of bits, but the recipient has to know which bits they are.  I see two approaches.

If the timing channel is the only communication, then the $m = log_2(n)$ bits has to combine both key data ($d$ bits) and position ($p$ bits).  If position indicates which group of $d$ bits we are leaking, then $p &gt;= log_2(k/d)$.  So for a 256 bit key this scheme requires that you be able to leak at least 9 bits at a time: 8 bits to indicate the key position and 1 for that key bit.  The position bits would be randomly generated.

Another approach would be to communicate the position differently: instead of using an RNG to select the position and include that in the leaked data, you could use data from the ciphertext if your threat model includes the attacker seeing that.  You could use the first $p$ bits of the ciphertext to choose/signal which key bits we are leaking, where $p = log_2(k/m)$.

In both cases, the solution to how long it takes to leak all $k$ bits of the key is given by the Coupon Collector's Problem, which is $O(n log n)$.  In the second example, this should come out to $O(k/m log(k/m))$.  Of course you don't have to wait to collect all of the sections.  Especially with a low bandwidth channel it would make sense to start brute-forcing as soon as feasible.