Tsukiyomi < rinnegan and Uzumaki heritage plus genjutsu barrier. Itachi once said to Kakashi that only a person of his blood or heritage who has the sharingan can brake his tsukiyomi, and since Kakashi was not an uchiha, he failed to break it. But Nagato is an Uzumaki, and both Uchiha and Uzumaki are descendent from the sage, so they are of the same heritage, plus rinnegan is not only a stronger doujutsu then the sharingan, but it is the ultimate level of sharingan mastery based on what we saw and heard from real madara, so then, this makes nagato fit the profile of the people who can break Tsukiyomi, based on Itachi's own words, though he was a top class liar, Itachi didn't have a reason or motive to lie in this case. Nagato also seems to specialize with barriers and more specifically, genjutsu barriers, he had these genjutsu barriers placed on his subordinates to prevent interogation, so it is possible that he has an even stronger one on himself. We have also never seen him get caught in a genjutsu, just three of his bodies, but not the real him, besides, those three paths could have broken the frog song if they wanted too (I have good reasons for saying this but it is irrelevant to the current topic). In any case, Nagato trumps tsukiyomi too.
