Resistive Random Access Memories (RRAMs) have gained high attention for a variety of promising applications especially the design of non-volatile in-memory computing devices. In this paper, we present an approach for the synthesis of RRAM-based logic circuits using the recently proposed Majority-Inverter Graphs (MIGs). We propose a bi-objective algorithm to optimize MIGs with respect to the number of required RRAMs and computational steps in both MAJ-based and IMP-based realizations. Since the number of computational steps is recognized as the main drawback of the RRAM-based logic, we also present an effective algorithm to reduce the number of required steps. Experimental results show that the proposed algorithms achieve higher efficiency compared to the general purpose MIG optimization algorithms, either in finding a good trade-off between both cost metrics or reducing the number of steps. In comparison with the RRAM-based circuits implemented by the state-of-the-art approaches using other well-known data structures the number of required computational steps obtained by our proposed MIG-oriented synthesis approach for large benchmark circuits is reduced up to factor of 26. This strong gain comes from the use of MIGs that provide an efficient and intrinsic representation for RRAM-based computing—particularly in MAJ-based realizations—and the use of techniques proposed for optimization.