Algid parse error, not a sequence

It means your key is not in PKCS#8 format. The easiest thing to do is to use the openssl pkcs8 -topk8 <...other options...> command to convert the key once. Alternatively you can use the PEMReader class of the Bouncycastle lightweight API.

I was having this same issue, and the format of the key was NOT the actual problem.
All I had to do to get rid of that exception was to call

java.security.Security.addProvider(
         new org.bouncycastle.jce.provider.BouncyCastleProvider()
);

and everything worked

You must make your PCKS8 file from your private key!

private.pem => name of private key file

openssl genrsa -out private.pem 1024

public_key.pem => name of public key file

openssl rsa -in private.pem -pubout -outform PEM -out public_key.pem

‫‪private_key.pem‬‬ => name of private key with PCKS8 format! you can just read this format in java

openssl pkcs8 -topk8 -inform PEM -in private.pem -out private_key.pem -nocrypt