Some problems just can't be solved in the time one wishes they take.
In your case, consider that modern processors have memory bandwidths of around 40 GB/s. (Give or take a small integer factor that isn't particularly important to the argument.) If you have $n=10,000, m=1,000$, then just loading all of the $F$ vectors into the processor requires accessing $8nm=80 MB$ of data in double precision. So just a single access to all of the data is going to take around 2 milliseconds. But you need to do that more than once per iteration, at least once for the computation of the right hand side of the Newton system and once for the computation of the matrix. You also need to write to these matrices and vectors. So it isn't unreasonable to say that all of this is going to cost you ten times the time of just one read-though, or 20 ms per iteration (again give or take a small factor). Then you also have to solve a linear system of size $1000\times 1000$, which takes 8MB to store, equivalent to another 0.2 ms. Solving a linear system surely takes many memory accesses, so at least another several milliseconds.
Then you have your Newton direction, at a cost of maybe 30 or 40 ms at the minimum, and you need to do a line search -- which requires computing multiple right hand side vectors which will again take 2 ms just to read the data for every residual evaluation, plus dots products, norm computations, etc. So maybe that gets you to maybe 50 ms per iteration just with data transfers.
If your problem had only $\beta_i=2$, then a Newton method would converge in one step, but for your problem it likely takes many more iterations -- say 20 or 40, and so you're already in the range of several seconds. That's not actually all that far away from what you see in practice.