If you currently have no indexes on your user table, then when you do a SELECT * FROM tUser WHERE Username='someuser' the DB has to do a full table scan to find that row. In other words, it has to look row by row through the table checking each row to see if Username='someuser'. This is inefficient. If you have 600K users in the table, then on average it will have to look at 300K user rows before finding your desired row every time you query it. So yes... Your problem is likely the lack of indexing if you don't have any, or are not indexing the correct fields.
How you index the table should be determined by how you look up users in the table (i.e. which fields you use to find rows in the table). Without knowing which fields are in the table (username? password? firstname? lastname? email address? etc.) and how you query the table, it's hard to say what your index(es) should be like.
Does a user enter a username/password on a login screen and then you look them up to see if there is a row in the table for that username/password combination? If so maybe you need an index on Username/Password combination.
Do you look users up sometimes by Firstname/Lastname? If so then maybe you need an index on Firstname/Lastname combination.
Do you look users up by email/password? Then maybe you need an index on email/password combination.
Do you every look users up by just username or just email? Then maybe you need an index on just username or just email, respectively.
Do you do all of the above? Then maybe you need multiple indexes.
The thing you need to watch out for with indexes is that while they make SELECTs, UPDATEs, and DELETEs run much faster (because it can quickly find a particular row in the table), it does so at the cost of making INSERTs run slower because it can no longer simply shove a new row into a table. If you have 4 indexes on the table then every time you do an INSERT it has to also go update all 4 indexes so that in the future it will know how to quickly find the row you just inserted.
Like everything in computing, there is always a trade off.