A fast non-cryptographic hash function that is "strong enough"? I'm designing a simple one-time-password mechanism for authentication against a possibly-insecure server - i.e. I don't want to use symmetric shared secrets.

The first idea that came into mind was using a hash-chain with a cryptographic hash function, where each device has a random $\text{key}$ and broadcasts 
$H^n(\text{key}), H^{n-1}(\text{key}), H^{n-2}(\text{key}), \ldots, H^{1}(\text{key}), \text{key}$.
However, storing the whole chain requires too much memory for my needs.

I found some techniques here and here to store only few elements from the chain ($H^{n-k}(\text{key}), H^{n-2k}(\text{key}), H^{n-3k}(\text{key}), ...$), and calculate the elements in between dynamically.
This converts the "space problem" to a "calculation cycles problem" - unfortunately all the cryptographic hash functions that I've checked require too many cycles (=too much power consumption) for my needs, considering the fact that I have to calculate them multiple times in order to save a significant amount of space.

I consider using less secure hash function for the dynamic hash calculation.
This hash will be used only for the elements "between" $H^{n-k}(\text{key}), H^{n-2k}(\text{key}), H^{n-3k}(\text{key}), ...$ so it has to be "unbreakable" only for $k$ time - suppose a key is generated every minute, finding $k$ sequential preimages in $k$ minutes should be "really hard" (but finding them in $10k$ minutes may be possible).

I don't care about second preimage resistance, or defending against very resourceful attackers.

Do you have any suggestions for a hash function? What about SipHash-2-4?
So what you need is a fast cryptgraphically secure hash function?
There are some.
If you're in hardware Keccak might be an option as it uses many bit-permutations.

If you're in software there are Skein and Blake2b/s/bp/sp. Skein was the fastest hash-function of the SHA-3 competition and Blake2 is the successor to BLAKE, the second fastest hash-function in the SHA-3 competition.

You might find this page helpful.