However, sometimes they have more money than their investment prospects can handle. Normally under those circumstances, they would buy treasuries from the federal reserve, which return the "risk-free rate". They always want to invest their money in things that return more than the risk-free rate, but sometimes they can't find enough stuff to invest in that they think will have a better return. In those cases, they're forced to buy treasuries.
Now, if the risk-free rate is negative, you might reasonably ask: Why doesn't the bank just keep cash? And the answer to that is that they're legally prevented from doing so. Banks have to maintain their capital reserves at the Fed, and the Fed pays them the "federal funds rate" on those reserves. So if they can't lend out the capital, they have to keep it with the Fed, where it earns whatever rate the Fed chooses to give them.
Some cursory research suggests this is not the case. The Federal Reserve website states: "Depository institutions must hold reserves in the form of vault cash or deposits with Federal Reserve Banks." 
How does what you said mesh with the notion that keeping cash might be riskier / more cumbersome than investing in the "risk-free" treasury bonds?
Banks are required by law to keep a portion of their assets on deposit in reserve. So if a bank has say, 1 billion in deposits, they might be required to maintain a balance with the Fed of 100 million.
What I think you're asking though is "why don't they just not keep the cash at the federal reserve". And the answer is that that's just not a thing you can do. Your bank maintains an account with the Fed - that's how it actually "stores" money. It can also physically store cash, but that comes with carrying costs (protecting it, etc.). Those carrying costs are one form of a negative interest rate.
At the end of the day, someone is storing the money somewhere. And the root-level money storer in the economy is the Fed. If the Fed wants to charge you 0.5%/year to store your money, what are your alternatives? You could keep physical cash. But then you have to protect it. You could invest in other assets, like stocks/bonds/mortgages, but those have risks. If you can't find any investments you like, and you don't want to physically store the cash, you don't really have any other choice.
No, they’re not. They must hold certain quantities of reserves with the Fed. But banks are free to hold the rest as cash in their vaults.
This is why many countries with negative rates still have zero deposit rates.