Gauss in Disquisitiones Arithmeticae (1799) does indeed express something close to what is now called mathematical formalism and structuralism. He writes:
"What is calculated (in the sense of things already counted) are not substances (thinkable objects for themselves), but relations between two objects counted two by two... The mathematician abstracts totally from the nature of the objects and the content of their relations; he is concerned solely with the counting and the comparison of the relations among themselves".
But it is hard to ascribe similar opinions to Kant, in fact his view was just the opposite. That concepts without intuitions are empty, and that (pure) intuitions for mathematical concepts are supplied by imaginative construction according to a priori schemata of space and time. In other words, relations are constructed only along with their intuitive objects. This led Kant to claim the a priori certainty for Euclidean geometry, something Gauss explicitly criticized him for:"Precisely the impossibility of deciding a priori between [Euclidean and non-Euclidean space] gives the clearest proof that Kant was not justified in asserting that space is just the form of our perception." Indeed, relationalization and formalization of mathematics in 19-th century went hand in hand with rejecting (notably by Frege and Hilbert) Kant's intuitive conception of it (which was retained more by Poincare and intuitionists).
Gauss had plenty of earlier sources to build on though. The abstractization of mathematics can be traced back to Vieta's Isagoge (1591). Bos writes in Redefining Geometrical Exactness, Ch.8:
"It was Viète who first introduced and promoted the idea that algebra was proper method for analysis of problems both in geometry, and in the theory of numbers... Viète usually reserved the term specious logistics for that part of his new algebra that dealt with abstract magnitude and in which therefore no assumptions coud be made about the actual effectuation of algebraic operations... Viète did not see algebra as a technique concerning numbers... but as a method of symbolic calculation concerning abstract magnitudes."
For more see Esteve's The Role of Symbolic Language in the transformation of Mathematics. The next thinker to advance relational/abstract view of mathematics, and Kant's chosen foil, was Leibniz. He is the one who called imaginary numbers and infinitesimals "useful fictions" and promoted the so-called "generality of algebra" (the term was coined by Cauchy), treating algebraic idenities as purely formal rules that apply regardless of the nature of the quantities involved. Peckhaus describes in Calculus Ratiocinator vs. Characteristica
"‘Abbreviating’ means that as soon as a characteristic sign has been established for a complex object, memory can be relieved of the burden of retaining all the characteristic elements of this object. Natural languages are not sufficient for this job of designating objects unambiguously. Only in the language of arithmetic and algebra has this idea been partially realized. All reasoning in these branches consists in using characters. Errors in reasoning prove to be miscalculations... He uses arbitrarily chosen letters according to the model of mathematics. This notation allows ‘calculating with concepts’ according to sets of rules, each of them forming a calculus ratiocinator."
Frege specifically names Leibniz's calculus ratiocinator as inspiration for his concept-script (predicate calculus). Generality of algebra was later extensively used by Euler, Lagrange, and Gauss himself, in "algebraic analysis" that preceded Weierstrassian one, see The Foundational Aspects of Gauss's Work by Ferraro:
"Finally, eighteenth-century functions were characterised in an essential way by the use of a formal methodology that it made it possible to operate upon analytical expressions, independently of their meaning. This formal methodology was based upon two closely connected analogical principles, the generality of algebra and the extension of rules and procedures from the finite to the infinite. The generality of algebra consisted of the following assumption: (GA) if an analytical formula was derived by using the rules of algebra, then it was thought to be valid in general"."
Peacock later renamed this into Principle of Permanence of Form in his Symbolical Algebra (1831):"Whatever form is Algebraically equivalent to another, when expressed in general symbols, must be true, whatever those symbols denote." The abstractization of algebra was further promoted, before Hilbert, by Hankel and Dedekind.