If your ssh key relies on RSA, then yes, you're relying on the difficulty of factoring numbers; which Shor's algorithm can perform efficiently. But only if the quantum computer has enough qubits. The needed number of qubits needed to factor is a multiple of the rsa key length. Unlike a regular computer, where you can finagle two computers with 2 gigs of memory to work like a single machine wiht 4 gigabytes of memory, so you can't just merge two 1024 qubit computers to get a 2048 qubit computer. And we're a long way off to having anything close to that.

The simplest solution is simply to increase the size of the key beyond that of the most advanced quantum computer (which is essentially today's approach ;) ). Also, you just need to exchange a symmetric key; Shor's algorithm is a special case, you don't get the exponential -> polynomial speedup[1] to encryption algorithms in general. So once you deliver the symmetric key in a secure way, using a quantum resistant algorithm, you can resume business as usual.

[1] Though in brute force searches, you can reduce the effective key length by 2. https://en.wikipedia.org/wiki/Grover%27s_algorithm

You can't have an an infinitely long key. Eventually the decripting process slows everything down to nothing.

Short and simple: yes.

Though the question is how relevant this is. Likely SSH will have moved to something more secure years before any quantum computer with sufficient computing power will become available.

Because that's the thing these scare-stories don't tell you: While the progress in quantum computing is moving very slowly, in recent years the progress in post quantum cryptography has been very fast.

A quantum computer with threatinging amounts of qubits could already exist as a secret military project today.

Can you elaborate more? In what sense? They are certainly vulnerable if you compromise the system which has them saved. Are they vulnerable to a brute force breach? Likely not, brute force is always a slow process, no matter how you speed it up. Is X vulnerable should always be phrased as Is X vulnerable to Y.

right, brute force your way in without a key

I would also add is there additional vulnerability just from an attacker examining the public key with crypto whatchahosy magic

I'm not sure I follow. A brute force attack generates a key which can then be tested against the target. This isn't magic, in fact, the more detailed answer above made the same argument essentially. Thought they provide a different argument suggesting that it may be possible to increase the ability to guess keys correctly.

I would think that if the rate of guesses is only one per second it would take eons to find the correct one. I was just wondering if there is an offline method. Just wondering how safe we can be when the news comes out.

I assume you are correct. I also assume you and I are somewhat safe. You have to consider the likely hood of an individual getting a hold of one of these devices in the near future. Then again you really have to ask if there is any reason you in particular will be targeted by someone with this technology.

Eventually everyone will be targeted. I have an unannounced web server serving a domain in the middle of internet nowhere and I get script attacks all the time. If some how this gets commercialized with no regulation criminals will open up shop for business practically the day after. Its like CRISPR: sure it can do some powerful things but so can your adversaries to you. I hate to think of the internet as a cloud of adversaries but that is really what it has become.

CRISPR fears are really overrated. It is nowhere near as mature as it needs to be. Further, you're less likely to make anything useful with it and more likely to just kill the organism you are trying to create. I work in a biotech lab, and we hardly ever use it and instead opt for manual plasmid knock in/down or tissue engineering techniques instead. The extent of work you have to put in to actually get something useful from CRISPER is prohibitive of it being used to target you and I.