The problem is that Calculus has little-to-no proof content (unless your course used a book like Spivak's). And depending on what kind of Linear Algebra course you took, it was either mostly computational and had little proof content, or it was used to introduce you to proofs. But even in the latter scenario, you wouldn't have enough exposure to proofs yet to easily jump into an advanced subject.
Proofs are the lingua franca of mathematics, but most students have to take multiple proof-based courses to develop even a moderate amount of comfort with mathematical rigor. And without understanding what makes a proof rigorous, you can't really do anything interesting in pure math.
The kind of math you learn before college is mostly "plug and chug". Someone gives you a recipe for how to solve a problem, and you apply that recipe. So long as you apply the recipe correctly, you get the correct result. This type of "math" continues into early college-level courses such as Calculus. In Calculus, it may not always be immediately obvious what recipe you need to apply to a given problem, but it's still mainly about combining a few recipes and some other tricks you've learned. With Linear Algebra, even if you're doing a proof-based Linear Algebra course, most of the proofs primarily revolve around algebraic manipulation techniques.
This way of looking at math -- as a tool that gives you a solution -- is useful if you want to study an applied area that uses mathematics, but not if you want to study mathematics itself. For instance, with Calculus and Linear Algebra, you know enough to dive into an area like Machine Learning or Computer Graphics, or probably several Engineering fields.
But studying mathematics means getting a deeper understanding of why the tools work, not just how to use them. It requires a very different mindset than what you have been taught so far.
The best recommendation would be to look at a book on elementary number theory, which it sounds like you already attempted to do. Number theory has a ton of problems that are easy to understand, but which don't have an easy solution. In fact, many famous problems in number theory remain unsolved. But you're not likely to be able to solve them without learning a lot more advanced mathematics.
It's not so much that understanding advanced mathematics is absolutely required to solve those problems. It's at least hypothetically possible that someone could solve these hard problems from first principles, knowing not much more than you already know. Possible but unlikely. Rome wasn't built over night, and even very brilliant people build on the foundations of those that came before them.
So the reason for studying a huge breadth of mathematics, rather than immediately jumping into some deep problem that looks interesting, is the breadth will give you more perspectives to look at the problem from, thus increasing the chance that you may figure out a creative solution.
However, many elementary number theory books are specifically tailored to students with little math background, and if you are struggling to understand the proofs in such a book, it means that you just don't have enough familiarity with proof, which will be an issue no matter what math subject you study. Your college has probably given some thought to developing a curriculum that will increase your familiarity with proof over time, so it's recommended you follow their curriculum.
Think of proof as a game. Right now, you probably don't even understand the rules of the game that well. Once you get to the point where you can play the game well enough that you are able to understand how expert players play it (even if you can't replicated what they do), then you can go study any advanced area of mathematics on your own. Until then, you need to focus on getting better at this game.
One more thought. You could go back and read Spivak's Calculus textbook. If you do so, you are likely to find the concepts familiar and foreign to you at the same time. Reading that book will make you realize that even in the subject of Calculus, there are so many important details that your previous instructor never taught you. Details that are not important if you will never major in math, but which are important if you want to truly understand the subject. And it's not like you will have to use Calculus much in the future. It's just one of many things you learn in math.
But what's important for you to understand is how a mathematician actually looks at Calculus, which is almost certainly very different than how you were taught. And the reason for that is because math professors believe their perspective is wasted on students who aren't going to become math majors. Ergo, you will not even get a good sense of how mathematicians look at math until you take the first course that only math majors take.
