Oh, you do need to install it. e.g. on arch: https://archlinux.org/packages/extra/x86_64/krun/

I do have both podman and crun installed, but I don't see any krun or libkrun packages for ubuntu unfortunately :/

That's unfortunate. I'm sorry, I should have checked that before recommending. Looks like your only option from an ubuntu host is to build from source.