Republicanism and Madison
Part of my problem with said assertions is that they usually are made in a way that shows a lack of understanding of semantics, history, and theory. Further, the phrase is typically deployed in way that 1) makes the two terms represent two different regime types (which is simply an incorrect assertion) and 2) supposedly tells us something about contemporary governance (usually something along the lines of why majority sentiment can be ignored).
Along those lines, I give you James Madison, from Vices of the Political System of the United States (written in April, 1787): “In republican Government the majority however composed, ultimately give the laws.”
Now, one has to readily grant that because of the limited suffrage of the day, Madison was clearly not talking about a majority of all inhabitants. However, he is clearly equating (and does elsewhere in the piece as well) “republican government” with “majority rule” of the electorate.
Just something to keep in mind when making the claim that “the US is a republic, not a democracy.”