select and lock random row from postgresql from Java application

I have a situation where i have table with around 500 accounts. These accounts are used for doing some financial transaction submissions. When transaction starts, i need to get an account from this table(any random account would work) and then lock that row so no other row will have access to this account until the operation is finished. Then do submit the transaction to external system and then unlock the account.

I have implemented this using following algorithm. All queries are executed in transactional context here.

//Get Random account
1. select * from gas_accounts where is_locked = false order by random() limit 1
//Lock that account using the primary key
2. update gas_accounts set is_locked = true, last_updated_at = current_timestamp where public_key = :publicKey
//unlock the account
3. update gas_accounts set is_locked = false, last_updated_at = current_timestamp where public_key = :publicKey

When running with 50 concurrent threads, the above function takes sometime around 50 seconds to return. Is there any better way to do this?