Optimizing query for large table with `rand()` ordering

I have a MySQL database running for a multiplayer game server and I've been trying to identify a performance bottleneck. I got the slow query logs and the slowest queries by time are like this (the matchmaking system):

select `accountID` from GameAccountProfile where `active`=1 and 
`lastActiveTime`0 and
`league`=4 and `protectedPeriod`>1482550190 and `lastActiveTime`>1481945090 and
`accountID`!=986702 and `accountID`!=10 and `accountID`!=10 and
`accountID`!=463126 and `accountID`!=184374 and `defenseRating`>=3.3530639 and
`defenseRating`=-8 and `level`<=2
order by rand() limit 1;

There are currently about 1.3 million rows in this table. I read that the rand() sorting may be a serious performance hit and when I ran an explain on it in MySQL Workshop on the query, it did highlight it in red as being a performance hit.

Also, I realized that the only index for any of these where conditions is on the account ID column. I'm considering adding a composite index on the "active", "inTutorial", "level", and "league" columns as they don't change often (arranged starting with the least often changed).

How can I get a random account ID with these conditions without using rand() in an order clause? I need to ensure all accounts get targeted equally but rand() seems to be a clear performance hit.

Is there any other way I can improve the performance of this query?

If you only want one it's easy. Just choose a random offset and get that one. It's very fast and because you don't need to sort the table at all:

$total = query("SELECT COUNT(*) FROM GameAccountProfile WHERE blah");
$offset = rand(0, $total-1);
$id = query("SELECT accountID FROM GameAccountProfile WHERE blah LIMIT $offset, 1");

StackExchange Database Administrators Q#159214, answer score: 4