algent Thanks, checked it out but did not work.
In the end I got help by joining gajim@conference.gajim.org they referred me to https://dev.gajim.org/gajim/gajim-plugins/-/wikis/OmemoGajimPlugin and gave the link to omemo plugin zip file.
In the end, all I need was to download the omemo zip from here https://ftp.gajim.org/plugins_1.3_zip/ which could then be installed from Gajim plugin settings. (For future reference, Solus is now on Gajim 1.3.3 so might need another version if this is read by someone in the future).
Also, their wiki lists a bunch of dependencies which are not available in Solus repo except python3-devel and libffi-devel, which I installed, but seems only the omemo zip from the link above is needed honestly.
Anyway, it works and I'm very happy, not having encryption would be too spooky, so great this is solved. 😄