And guess what, these problems are hard for me.
- Should I spend more time on hard ones before giving up?
- Should I memorise solutions by heart to get techniques?
- What could I do if I get stuck?
I am afraid there is no easy answer to questions like this. Hard work and innate ability are both ingredients, but nobody will be able to tell you how hard you have to work to solve a problem, or how difficult a problem you will be able to solve on your own (and after all, there is a limit, because you only live so long).
Memorisation can help, but many (most?) successful problem solvers do not memorise very much. Practice is ten times as important as memorisation. And figuring out how to solve a problem on your own is ten times as valuable as looking up a solution. But sometimes it will take you more than ten times as long to discover the solution on your own, and you are only human. We all look up a solution from time to time. But you should try as hard as you can to make it an exception rather than a rule.
There are some general rules, but trying to be too precise misses the point. There is no general algorithm for problem solving. People mostly just learn by doing. You find tricks you like, and you try applying them to new problems you find. Sometimes the trick is good and you keep it around. Richard Feynman famously got a reputation for doing hard integrals, when on many occasions he was just applying a trick nobody else knew about. Some tricks are so well-known to be useful we put them in books and teach classes about them.
I'll be honest with you and say that the only thing that jumps out at me when I look at that fraction is "difference of two squares". The thinking part of my brain wants to say something like "I have no idea how to add up a bunch of square roots, so I had better find some way to express $n-\sqrt{n^2-1}$ as a square of something".
Difference of two squares tells me $n^2-1 = (n+1)(n-1)$. Maybe that's useful maybe it isn't. It's not a square, which sucks. What would a square look like? Well $(\sqrt{n}+X)^2 = n+2\sqrt{n}X + X^2$. I picked $\sqrt{n}$ so I'd get an $n$ term there. Another thing I noticed is that $(n+1) + (n-1) = 2n$. In fact that $\sqrt{n}$ is reminding me of something I've seen before.
If you add two square roots and square it, the "square-root-ness" goes down. What do I mean? This identity:
$$(\sqrt{a}+\sqrt{b})^2 = a+b + 2\sqrt{ab}$$
You use this sometimes if you want to solve an equation like $\sqrt{x+1} + \sqrt{x} = 1$. Anyway in this case we can pattern match a bit and say "I want to make $ab$ like $n^2-1$". Well what about $a=n-1$ and $b=n+1$. Well then $a+b=2n$. Oh, we're done:
$$n+\sqrt{n^2-1} = (\sqrt{n-1}+\sqrt{n+1})^2/2$$
Wait! I misread the question! There's actually a minus sign, but... the minus sign doesn't make a difference. We're done! The sum telescopes so you can work out the rest easily.
There isn't a magic formula that will tell you how to do this. You just figure it out by practicing a lot. Most people can do this sort of problem if they work at it. You probably have a limit, but it's also probably higher than you think it is. There are words like "generalisation" and "abstraction" that people could use to document what was going through my head when I solved this problem. But it's not really how you learn to solve the problem. You learn by doing, and by association.
Addendum: There really is no algorithm
I noticed this while proof reading my answer, and I couldn't resist pointing it out. I gave an example earlier of an equation $\sqrt{x+1} + \sqrt{x} = 1$. I promise I picked it randomly. People sometimes try to teach you that there are simplifications you should always do. Rationalising the denominator is one (you used it in your question). But this is a good example where you should do the exact opposite! By "un-rationalisting the denominator", you get:
$$\frac{1}{\sqrt{x+1} - \sqrt{x}} = 1 \implies \sqrt{x+1}-\sqrt{x} = 1$$
and not much more work is needed to get a solution. Much easier than repeated squaring!