Start by separating the IP address from the sending domain. Reverse DNS belongs to the IP's reverse zone, normally controlled by your hosting provider or ISP. Ask them to set the PTR for your outbound IP to a mail hostname, and make sure that hostname resolves back to the IP.
SPF and DKIM are different. Their records need to be published under the relevant sending domains, so whether you can do that yourself depends on which domain the application uses and who controls it. DMARC checks alignment with the visible From domain, so that matters too.
Check the actual Spamhaus listing and its removal requirements rather than assuming missing DKIM caused it. Fixing DNS is worthwhile, but it may not automatically clear a listing or guarantee delivery.
4c!ferrulepocket_853:
Also check which public IP actually makes the outbound connection. It may not be the address you expect if traffic goes through a gateway.