Generate random values in C#

This should do the trick. (It's an extension method so that you can call it just as you call the normal Next or NextDouble methods on a Random object).

public static Int64 NextInt64(this Random rnd)
{
    var buffer = new byte[sizeof(Int64)];
    rnd.NextBytes(buffer);
    return BitConverter.ToInt64(buffer, 0);
}

Just replace Int64 with UInt64 everywhere if you want unsigned integers instead and all should work fine.

Note: Since no context was provided regarding security or the desired randomness of the generated numbers (in fact the OP specifically mentioned the Random class), my example simply deals with the Random class, which is the preferred solution when randomness (often quantified as information entropy) is not an issue. As a matter of interest, see the other answers that mention RNGCryptoServiceProvider (the RNG provided in the System.Security namespace), which can be used almost identically.

Use Random.NextBytes() and BitConverter.ToInt64 / BitConverter.ToUInt64.

// Assume rng refers to an instance of System.Random
byte[] bytes = new byte[8];
rng.NextBytes(bytes);
long int64 = BitConverter.ToInt64(bytes, 0);
ulong uint64 = BitConverter.ToUInt64(bytes, 0);

Note that using Random.Next() twice, shifting one value and then ORing/adding doesn't work. Random.Next() only produces non-negative integers, i.e. it generates 31 bits, not 32, so the result of two calls only produces 62 random bits instead of the 64 bits required to cover the complete range of Int64/UInt64. (Guffa's answer shows how to do it with three calls to Random.Next() though.)

Here you go, this uses the crytpo services (not the Random class), which is (theoretically) a better RNG then the Random class. You could easily make this an extension of Random or make your own Random class where the RNGCryptoServiceProvider is a class-level object.

using System.Security.Cryptography;
public static Int64 NextInt64()
{
   var bytes = new byte[sizeof(Int64)];    
   RNGCryptoServiceProvider Gen = new RNGCryptoServiceProvider();
   Gen.GetBytes(bytes);    
   return BitConverter.ToInt64(bytes , 0);        
}