In my opinion, some may disagree with me, but your best bet would be to keep a small group of sajicas in here. 1 male and 3-4 females would be ideal. This way the male will be a bit distracted from his mate (less likely to murder her) and the pair bonds a bit in their defense from the others. I think this would be better than going for another cichlid species. The tank probably won't have room for 2 pairs, and unless you put a larger more aggressive cichlid, the pair would probably kill a random lone cichlid. But, putting a larger more aggressive cichlid with them opens up a whole new world of possible problems, and I don't think the tank is large enough for that.
So what I would do, is get a group of 4-5 sajica young, let them grow up together, and let a pair form naturally. Have some dithers in there as well like livebearers. I had a setup like this with my panamensis and it worked great, the pair would breed and the other 2 panamensis were not killed. I eventually sold the 2 extras, thinking it would be better to just have the pair, and that is when the male killed his mate. This was in first a 5' 70 gallon, then a 4' 90 gallon (where he killed her).