I took a closer look and the iOS extension supports entering a “session link” which allows the Kagi redirect to work in private windows. Entering it is a bit cumbersome—you have to first open a private window and then any random page so you can see the extension button in the address bar, at which point you can tap it and then the Kagi icon to get to the session link field—but it appears to stick after that and the redirect works as expected (although you do get a brief flash of Google or whatever — they suggest changing it to DDG which looks a bit smoother).

Agree that it feels hacky, but sometimes you just have to take what you can get.

You can generate a Kagi login link with a token and save that to your favourites. Then, click that link in the new private tab window before searching.

The Kagi Search app/extension linked above can persist your session link in its settings and thus works in private mode or after clearing all cookies.